Stone Arrangement

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Playing with stones is an art, and the player is an artist...
— FireGhost.

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

Please read the guidelines before commenting.



  • -1
    tuan1234  commented on Jan. 18, 2024, 7:42 a.m.

    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ờ


  • 6
    HuyyTD  commented on June 21, 2023, 3:40 a.m.

    tên bài bủh quá


  • -14
    lpd0201  commented on June 6, 2023, 5:48 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 3
      connornguyxn  commented on June 13, 2023, 9:40 a.m.

      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é.


      • 2
        dangduc2102  commented on Aug. 12, 2023, 1:36 p.m.

        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


        • 2
          nhatquang1310  commented on Oct. 16, 2023, 2:35 p.m.

          tôi yêu Lê Nguyễn Quỳnh Anh