E. Candy Eating
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It is the day after a very successful Halloween and Charlie managed to receive so much candy that he can't decide when he should eat all of it!

The candy that Charlie has can be divided into $$$n$$$ types numbered $$$1, \dots, n$$$. For some candy type $$$i$$$, let $$$k_i$$$ denote the amount of candy $$$i$$$ that Charlie has, and let $$$c_i$$$ denote the tastiness of each piece of candy of type $$$i$$$. The total tastiness of Charlie's consumptions is given by the sum of the tastiness of each piece of candy that Charlie eats. Charlie would love to eat all of the candy he has, but unfortunately there are the following restrictions:

  • All of the candy expires after $$$d$$$ days, meaning that after the $$$d$$$-th day, Charlie cannot eat any more of his candy.
  • Charlie's parents won't allow him to eat more than $$$x$$$ pieces of candy in a given day.
  • Charlie will not eat two candies of the same type on the same day.

Please help Charlie and determine the maximum total tastiness he can achieve if he eats his candy optimally!

Input

The first line of input will contain $$$n$$$, $$$d$$$, and $$$x$$$ ($$$1 \leq n, d, x \leq 2 \cdot 10^5$$$) — the number of types of candies, the number of days before all candies expire, and the maximum number of candies Charlie can eat a day.

The next line of input consists of $$$n$$$ space-separated integers $$$k_1, k_2, \dots, k_n$$$ ($$$1 \leq k_i \leq 2 \cdot 10^5$$$) — the amount of candy that Charlie has of each type.

The last line consists of $$$n$$$ space-separated integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \leq c_i \leq 2 \cdot 10^5$$$) — the tastiness of a piece of candy of each type.

Output

Output a single integer denoting the maximum total tastiness that Charlie could achieve by eating the candies optimally.

Examples
Input
8 3 3
1 1 2 1 3 2 2 1
2 7 6 9 4 3 5 8
Output
54
Input
1 200000 200000
200000
200000
Output
40000000000