Alob and Bice are the best stone players in the world! On the occasion of VNOI Cup, Alob and Bice have agreed to meet at Ha Long Bay to discuss stone-graphy.
Alob and Bice each own ~n~ stones, each with a number written on it. They will arrange their stones into a sequence, with ~a_i~ being the number written on the ~i~-th stone of Alob, and ~b_j~ being the number written on the ~j~-th stone of Bice. We define the highness of an arrangement as ~\sum \limits_{i = 1}^n \max(a_i, b_i)~.
Alob and Bice agree that they want to rearrange their stones so that the highness achieves the maximum value. Please help Alob and Bice!
Input
Each input will consist of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10^3~) — the number of test cases of the problem. The description of the test cases follows.
The first line of each test case contains a positive integer ~n~ (~1 \le n \le 10^5~) — the number of stones that Alob and Bice own.
The second line of each test case contains ~n~ positive integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) — the numbers written on Alob's stones.
The third line of each test case contains ~n~ positive integers ~b_1, b_2, \ldots, b_n~ (~1 \le b_i \le 10^9~) — the numbers written on Bice's stones.
The sum of ~n~ over all test cases does not exceed ~10^5~.
Output
For each test case, output a single integer — the maximum highness that can be achieved by arranging the stones.
Scoring
If you solve this problem, you will receive ~1000~ points.
Sample Input 1
2
3
1 4 3
3 5 2
2
4 5
7 9
Sample Output 1
12
16
Notes
In the first test case, we can rearrange Alob's stones to ~[3, 1, 4]~, and rearrange Bice's stones to ~[3, 5, 2]~, then the highness of this arrangement will be ~\max(3, 3) + \max(1, 5) + \max(4, 2) = 3 + 5 + 4 = 12~.
In the second test case, we can rearrange Alob's stones to ~[5, 4]~, and rearrange Bice's stones to ~[9, 7]~, then the highness of this arrangement will be ~\max(5, 9) + \max(4, 7) = 9 + 7 = 16~.
Comments
ac rồi vào "bài nộp tốt nhất" sau đó vào "mã nguồn" của "buivietthanh" có bất ngờ
tên bài bủh quá
This comment is hidden due to too much negative feedback. Show it anyway.
Bài này gồm nhiều testcase với mỗi input, bạn đọc kĩ lại đề và test mẫu nhé.
góp ý rất bổ ích cảm ơn bạn rất nhiều. chúc bạn một ngày an lành
tôi yêu Lê Nguyễn Quỳnh Anh
This comment is hidden due to too much negative feedback. Show it anyway.