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 1\,000\,000)~, 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 1\,000\,000)~, 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~.