Problem:

 

In ancient China, there is a story about Kong Rong declining pears. Now Pablo meets a similar problem, though it is a little bit complex.Pablo??s father bought a lot of pears and divided these pears into a few groups. In every group, the pears are put upright in the order of their weight ( the heaviest are put on the table with the second heaviest put upon it, and so on), and in the same group the absolute weight difference between two nearby pears is same.

 

Father asks Pablo to take k pears (of course, he can only take the upper part of each group first). Our lovely Pablo has just read the story about Kong Rong, so he decided to take out k pears whose total weight is the lightest. Can you help him?

 

Input:

 

The input consists of several test cases. Each test case consists of three lines:

The first line consists of the number of the groups N (1=< N <= 5000) and K(1=<K<=10000), the times which Pablo should take.

The second line contains N integers, and the ith integer refer to the weight of the lightest pear in the ith group.

The third line also contains N integers, and the ith integer refer to the absolute weight difference between two nearby pears in the ith group.

 

Output:

 

In one line: the total weight of the k pears which Pablo should take. 

 

Sample input:

 

2 3

5 1

10 5

 

4 4

3 5 6 6

2 8 2 2

 

Sample output:

 

12

19