Once Maggu went for an adventurous trip to Mysteryland. Mysteryland is full of mysteries. There are n doors for entering into Mysteryland. Maggu has to open at least 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 at most v[i]. Needless to say that Mysteryland 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 i.e. 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 at least d doors. He can 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 few 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

For the second test case, the configuration of keys according to doors can be as follows -1, 1, 2. He only needs 2 Mystery powers for doing this.

For the last test case: For opening two doors, You can use key configuration 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 configuration of 1 -1 1 2 (reducing the second door number by 2), Then use -1, 1, 2 for opening 3 doors.