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?
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.
In one line: the total weight of the k pears which Pablo should take.
3 5 6 6
2 8 2 2