M. Balloon Market
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

This year, Pedro was invited to participate in a programming competition that will take place in a very, very distant country. Fortunately, he has already secured his ticket, which includes $$$N$$$ layovers in different countries.

To cover the costs of the trip, he decided to take a suitcase in which he can carry a maximum of $$$K$$$ balloons that he has left over from a previous competition, in order to sell them during the layovers of the trip. Since obtaining balloons in other countries is not so easy, Pedro decided that he will not add more balloons into his suitcase at any of the layovers.

Pedro knows that in the country he will visit during the $$$i$$$-th layover, he can sell each balloon for $$$V_i$$$ pesos (Argentine currency), but there is a problem: he can only enter with up to $$$C_i$$$ balloons without having to pay taxes. For each extra balloon, he will have to pay the Carnival Products Trade Tax, which costs $$$P_i$$$ pesos per extra balloon.

Pedro wants to know what the maximum net profit he can obtain is.

Input

A line with two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$, $$$1 \leq K \leq 10^{9}$$$), representing the number of layovers in the trip and the maximum number of balloons that Pedro can carry in his suitcase.

Then a line with $$$N$$$ integers: $$$V_1, V_2, \dots, V_N$$$ ($$$0 \leq V_i \leq 10^{9}$$$), the selling price of a balloon in the country he visits during the $$$i$$$-th layover, in pesos.

Then a line with $$$N$$$ integers: $$$C_1, C_2, \dots, C_N$$$ ($$$0 \leq C_i \leq 10^{9}$$$), the number of balloons that can be brought in for free at the $$$i$$$-th country.

Finally, a line with $$$N$$$ integers: $$$P_1, P_2, \dots, P_N$$$, ($$$0 \leq P_i \leq 10^{9}$$$), the tax that must be paid for each excess balloon when entering the $$$i$$$-th country, in pesos.

Output

A line with an integer, the maximum amount of money (in pesos) that Pedro can earn from selling balloons.

Example
Input
5 6
5 7 8 8 10
2 0 3 0 2
2 2 2 1 2
Output
27
Note

In the example, Pedro could carry in his suitcase $$$6 \leq K$$$ balloons, to sell three in the first city at a price of $$$ \$5 $$$ each, one in the third city for $$$ \$8 $$$, and the remaining two in the last city for $$$ \$10 $$$.

In this way, he would obtain gross income of $$$ 3 \cdot \$5 + 1 \cdot \$8 + 2 \cdot \$10 = \$43 $$$ and would pay a total of $$$ 4 \cdot \$2 + 3 \cdot \$2 + 0 \cdot \$2 + 2 \cdot \$1 + 0 \cdot \$2 = \$16 $$$ in taxes.

Thus, he would have $$$ \$43 - \$16 = \$27 $$$ in net profit, which is the maximum possible in this example.