You are the urban designer for a city with $N$ piles of candy that have different heights, $H_i$, and are tasked with building a wall to hide them.

You will be penalized for your inaccuracy in building a wall to hide each of these piles, $C_i$.

Specifically, you will be fined $C_i\times |S_i-H_i|$, where $S_i$ is the height that you build the final wall for the $i^{\text{th}}$ pile of candy. (Showing the candy or hiding scenic scenery is equally bad.)

Each pillar of the wall has an initial height of $0$.

Additionally, you can only change the height of a given wall up to $K$ times along its length (i.e., set the heights of all the pillars of the wall from $[i,N]$ to a height).

Find the minimum cost for this wall.

Input Specification

The first line will contain $N$ $(1\le N\le 150)$ and $K$ $(1\le K\le 150)$, the number of piles of candy that need to be covered and the number of changes you can make.

The second line will contain $N$ space-separated integers, $C_i$ $(1\le C_i\le 1000000)$, the cost for each difference in height between the piles of candy and wall.

The third line will contain $N$ space-separated integers, $H_i$ $(0\le H_i\le 1000000)$, the optimal height for this pillar.

Output Specification

Output the minimum cost to be fined for building this wall.

Sample Input

5 1
1 10 3 5 2
1 10 4 3 2

Sample Output

70

Explanation for Sample Output

Note that there are multiple valid solutions yielding the minimum cost.

Here is one valid solution:

Spend the first and only move to set the height for all pillars from $[2,N]$ to $9$, resulting in a total cost of $70$.