Read problems statements [Hindi] ,[Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

Appy loves balloons! She wants you to give her balloons on each of $N$ consecutive days (numbered $1$ through $N$); let's denote the number of balloons Appy wants on day $i$ by $A_{i}$. The problem is that you only have $M$ balloons. Fortunately, you can give her candies instead of balloons as well. On each day $i$, Appy accepts $B_{i}$ candies per each balloon you do not give her — formally, if you give Appy $X_{i}$ balloons on day $i$, then you have to give her $C_{i} = \mathrm{max}(0, A_{i} - X_{i}) \cdot B_{i}$ candies as well.

Your task is to minimize the maximum number of candies you give Appy on some day — find the minimum possible value of $\mathrm{max}(C_{1}, C_{2}, C_{3}, ..., C_{N})$.

------ Input ------
The first line of the input contains two space-separated integers $N$ and $M$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$.
The third line contains $N$ space-separated integers $B_{1}, B_{2}, \dots, B_{N}$.

------ Output ------
Print a single line containing one integer — the minimum value of $\mathrm{max}(C_{1}, C_{2}, C_{3}, ..., C_{N})$.

------ Constraints ------
$1 ≤ N ≤ 10^{5}$
$0 ≤ M ≤ 10^{18}$
$0 ≤ A_{i} ≤ 10^{9}$ for each valid $i$
$0 ≤ B_{i} ≤ 10^{9}$ for each valid $i$

------ Subtasks ------
Subtask #1 (27 points):
$1 ≤ A_{i} ≤ 10$ for each valid $i$
$1 ≤ B_{i} ≤ 10$ for each valid $i$

Subtask #2 (73 points): original constraints

----- Sample Input 1 ------
5 3
1 2 3 4 5
1 2 3 4 5
----- Sample Output 1 ------
15
----- explanation 1 ------
If you give Appy $0, 0, 0, 1, 2$ balloons on days $1$ through $5$, then the required numbers of candies on each day are $1, 4, 9, 12, 15$. The maximum number of candies is $15$, required on day $5$.

见题面

见题面