time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given two arrays aa and bb both consisting of nn positive (greater than zero) integers. You are also given an integer kk.

In one move, you can choose two indices ii and jj (1≤i,j≤n1≤i,j≤n) and swap aiai and bjbj (i.e. aiai becomes bjbj and vice versa). Note that ii and jj can be equal or different (in particular, swap a2a2 with b2b2 or swap a3a3 and b9b9 both are acceptable moves).

Your task is to find the maximum possible sum you can obtain in the array aa if you can do no more than (i.e. at most) kk such moves (swaps).

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤2001≤t≤200) — the number of test cases. Then tt test cases follow.

The first line of the test case contains two integers nn and kk (1≤n≤30;0≤k≤n1≤n≤30;0≤k≤n) — the number of elements in aa and bb and the maximum number of moves you can do. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤301≤ai≤30), where aiai is the ii-th element of aa. The third line of the test case contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤301≤bi≤30), where bibi is the ii-th element of bb.

Output

For each test case, print the answer — the maximum possible sum you can obtain in the array aa if you can do no more than (i.e. at most) kk swaps.

Example

input

Copy

5
2 1
1 2
3 4
5 5
5 5 6 6 5
1 2 5 4 3
5 3
1 2 3 4 5
10 9 10 10 9
4 0
2 2 4 3
2 4 2 3
4 4
1 2 2 1
4 4 5 4

output

Copy

6
27
39
11
17

Note

In the first test case of the example, you can swap a1=1a1=1 and b2=4b2=4, so a=[4,2]a=[4,2] and b=[3,1]b=[3,1].

In the second test case of the example, you don't need to swap anything.

In the third test case of the example, you can swap a1=1a1=1 and b1=10b1=10, a3=3a3=3 and b3=10b3=10 and a2=2a2=2 and b4=10b4=10, so a=[10,10,10,4,5]a=[10,10,10,4,5] and b=[1,9,3,2,9]b=[1,9,3,2,9].

In the fourth test case of the example, you cannot swap anything.

In the fifth test case of the example, you can swap arrays aa and bb, so a=[4,4,5,4]a=[4,4,5,4] and b=[1,2,2,1]b=[1,2,2,1].

解题说明：此题可以采用贪心算法，先对数组排序，然后用a中最小的值去替换b中最大的值，不断循环直到交换k个数即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>

using namespace std;

int T, n, k, a[50], b[50], ans;

int main()
{
	cin >> T;
	for (int i = 0; i<T; i++) 
	{
		cin >> n >> k;
		ans = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> a[i];
		}
		for (int i = 0; i < n; i++)
		{
			cin >> b[i];
		}
		sort(a, a + n); 
		sort(b, b + n);
		for (int j = 0; j<k; j++)
		{
			if (b[n - j - 1] < a[j])
			{
				break;
			}
			a[j] = b[n - j - 1];
		}
		for (int i = 0; i < n; i++)
		{
			ans += a[i];
		}
		cout << ans << endl;
	}
	return 0;
}