Once Maggu went for an adventerous trip to mysteryland. Mysteryland is full of mysteries. There are n doors for entering into mysteryland. Maggu has to open atleast d doors to enter into mysteryland. Each door of mysteryland can only be opened by specific mystery key. Each of the door has a number lock on it and door opens only by a key of that number.

As Maggu is a small boy, he is given a mystery power for each door. A mystery power is as follows, He can increase or  decrease the number of key of i^th door by atmost v[i]. Needless to say that msyteryland is so mysterious that keys to the locks are not fixed, they could be any integer (No need to be positive). But there is a problem, no two doors of the doors of mysteryland can be opened by same numbered keys ie if there are two or more doors that have same key, then only the first door will open. So he wants to apply mystery power operations so as to open atleast d doors. He can a apply a mystery operation on any of the door and as much times as he wishes.

As he is in haste for doing adventure, he wants to do this by using as less Mystery power operations as possible. Find out the minimum number of mystery power he needs to apply to enter into mysteryland so that he could enjoy himself :)

Input

First line of the input contains T denoting number of test cases (1 <= T <= 20).
For each test case, you are given 3 lines as follows.
First line contains two space separated integers n and d. (n will be between 1 and 50 inclusive), (1 <= d <= n)
Then next line contains n integers denoting the number written on the i^th lock. (each number will be between 1 and 1000 inclusive.
The next line contains n space separated integers denoting v[i]. (1 <= v[i] <= 5).

Output

For each test case, output a single line representing the answer to the problem.

Example

Input:
4
3 2
5 1 3
1 1 1
3 3
1 1 1
2 1 1
4 4
1 1 1 2
1 2 1 1
4 3
1 1 1 2
1 2 1 1
Output: 
 0
 2
 2
 1

Explanation of the test case. For the second test case, the configuation of keys according to doors can be as follows -1, 1, 2.
He only needs 2 Mystery powers for doing this.
Explanation of last test case: For opening two doors, You can use key configutation of 0, 1, 1, 2 (reducing the first door 
number by 1). Then use 0, 1, 2 keys to open 3 doors. 
You can also use key configutation of 1 -1 1 2  (reducing the second door number by 2), Then use -1, 1, 2 for 
opening 3 doors.