Schedule

Kozak Vus recently established his own company, which is expanding rapidly and now employs many people.

He has assigned $n$ tasks to his employees. Each task $i$ is characterized by two parameters: $r_i$ and $c_i$. Here, $r_i$ represents the deadline by which the $i$-th task should be completed, and $c_i$ indicates the importance of the task (with higher values of $c_i$ signifying greater importance).

Additionally, Kozak Vus has defined an integer constant $k$.

The employees need to determine an array $e$ of $n$ non-negative numbers such that the following expression is minimized:

Here, $\max (e)$ denotes the maximum value in the array $e$.

Kozak Vus is not interested in the array $e$ itself but wants to know the minimum possible value of the expression above.

Assist Kozak Vus's employees in solving this problem.

Input

The first line contains two integers $n$ and $k$ ($1\le n\le 10^6,0\le k\le 10^9$) — the number of tasks assigned by Kozak Vus to the employees, and the constant $k$.

The second line contains $n$ integers $r_1,r_2,\dots ,r_n$ ($0\le r_i\le 10^6$) — the array $r$.

The third line contains $n$ integers $c_1,c_2,\dots ,c_n$ ($0\le c_i\le 10^6$) — the array $c$.

Output

Output a single number — the minimum possible value of the expression ${\sum }_{i=1}^n|r_i-e_i|\cdot c_i+\max (e)\cdot k$.

Examples

Note

In the first example, the array $e$ that achieves the minimum value is $[1,2,3]$. The minimum value is $|1-1|\cdot 1+|2-2|\cdot 2+|3-3|\cdot 3+3\cdot 1=3$.

In the second example, the array $e$ that achieves the minimum value is $[0,0,0]$. The minimum value is $|1-0|\cdot 3+|2-0|\cdot 2+|3-0|\cdot 1+0\cdot 100=10$.

In the third example, the array $e$ that achieves the minimum value is $[1,2,2]$. The minimum value is $|1-1|\cdot 1+|2-2|\cdot 2+|3-2|\cdot 3+2\cdot 5=13$.

Scoring

1. ($8$ points): $c_i=0$;

2. ($15$ points): $c_i=1$;

3. ($30$ points): $n\le 1000$;

4. ($15$ points): $r_i\le 100$;

5. ($32$ points): no additional constraints.