Zeroing

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk has two arrays — \(a\) and \(b\), each of length \(n\). He needs to zero all the elements of the array \(a\).

In one operation, Zenyk can decrease any value \(a_i\) by 1. Such an operation will cost him \(b_i\) hryvnias.

Fortunately, Marichka agreed to help him. She can at any moment perform a cyclic right shift of the array \(a\). But Marichka is very busy, so she can do this no more than \(k\) times.

The plan is as follows: first, Zenyk will make some subtractions. Then Marichka will come and make a cyclic shift of the array \(a\): the first element of array \(a\) will become equal to the last element, the second element will become equal to the first, the third — to the second, and so on. Note that Marichka shifts only the array \(a\), leaving the array \(b\) unchanged. After that, Zenyk will again make some subtractions. Then Marichka will come again and make another cyclic shift, after which Zenyk will continue subtracting. And so on. In total, Marichka can make no more than \(k\) cyclic shifts.

You need to determine the minimum amount Zenyk will pay so that after all possible shifts and subtractions, all elements of the array \(a\) become equal to zero.

Input

The first line contains 2 integers \(n\) and \(k\) — the size of the array and the number of operations Marichka can perform.

The next line contains \(n\) integers — the array \(a\).

The next line contains \(n\) integers — the array \(b\).

Output

Output a single integer — the minimum cost of zeroing the array \(a\).

Constraints

\(1 \leq n \leq 5 \cdot 10^5\),

\(0 \leq k \leq 10^9\),

\(0 \leq a_i, b_i \leq 10^6\).

Grading consists of the following blocks:

• 1 point for each example from the problem statement,

• 8 points: \(k = 0\),

• 11 points: \(k \geq n\),

• 20 points: \(n, k \leq 10^3\),

• 24 points: \(b_i \leq b_{i+1}\),

• 36 points: no additional constraints.

Points for a block are awarded only if your program passes all tests in the block.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 2 4 7 4 7 1 2 2 1	22

Notes

In this example, the minimum cost can be achieved as follows:

1. Subtract 4 from the first element and 7 from the last element, paying \(4 \cdot 1 + 7 \cdot 1 = 11\). After this, the array becomes \((0, 7, 4, 0)\).

2. Perform a cyclic right shift — \((0, 0, 7, 4)\).

3. Subtract 4 from the last element, paying \(4 \cdot 1 = 4\), the array becomes \((0, 0, 7, 0)\).

4. Perform a cyclic right shift — \((0, 0, 0, 7)\).

5. Subtract 7 from the last element, paying \(7 \cdot 1 = 7\), the array becomes \((0, 0, 0, 0)\).

The total price paid is \(11 + 4 + 7 = 22\).