Schedule#10469

Schedule

2 seconds

256 megabytes

Easy

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}$ r_i and $c_{i}$ c_i. Here, $r_{i}$ r_i represents the deadline by which the $i$ -th task should be completed, and $c_{i}$ c_i indicates the importance of the task (with higher values of $c_{i}$ 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:

i = 1 \sum n ∣ r_{i} - e_{i} ∣ \cdot c_{i} + max (e) \cdot k =

\sum_{i=1}^{n} |r_i - e_i| \cdot c_i + \max(e) \cdot k =

= ∣ r_{1} - e_{1} ∣ \cdot c_{1} + ∣ r_{2} - e_{2} ∣ \cdot c_{2} + \dots + ∣ r_{n} - e_{n} ∣ \cdot c_{n} + max (e) \cdot k

= |r_1 - e_1| \cdot c_1 + |r_2 - e_2| \cdot c_2 + \dots + |r_n - e_n| \cdot c_n + \max(e) \cdot k

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 \leq n \leq 1 0^{6}, 0 \leq k \leq 1 0^{9}$ 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}$ r_1, r_2, \dots, r_n ( $0 \leq r_{i} \leq 1 0^{6}$ 0 \le r_i \le 10^6) — the array $r$ .

The third line contains $n$ integers $c_{1}, c_{2}, \dots, c_{n}$ c_1, c_2, \dots, c_n ( $0 \leq c_{i} \leq 1 0^{6}$ 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$ \sum_{i=1}^{n} |r_i - e_i| \cdot c_i + \max(e) \cdot k.

Examples

Example 1

Example 2

Example 3

Note

In the first example, the array $e$ that achieves the minimum value is $[1, 2, 3]$ [1, 2, 3]. The minimum value is $∣1 - 1∣ \cdot 1 + ∣2 - 2∣ \cdot 2 + ∣3 - 3∣ \cdot 3 + 3 \cdot 1 = 3$ |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]$ [0, 0, 0]. The minimum value is $∣1 - 0∣ \cdot 3 + ∣2 - 0∣ \cdot 2 + ∣3 - 0∣ \cdot 1 + 0 \cdot 100 = 10$ |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]$ [1, 2, 2]. The minimum value is $∣1 - 1∣ \cdot 1 + ∣2 - 2∣ \cdot 2 + ∣3 - 2∣ \cdot 3 + 2 \cdot 5 = 13$ |1-1| \cdot 1 + |2-2| \cdot 2 + |3-2| \cdot 3 + 2 \cdot 5=13.

Scoring

( $8$ points): $c_{i} = 0$ c_i = 0;
( $15$ points): $c_{i} = 1$ c_i = 1;
( $30$ points): $n \leq 1000$ n \le 1000;
( $15$ points): $r_{i} \leq 100$ r_i \le 100;
( $32$ points): no additional constraints.