1879B. Chips on the Board

constructive algorithms, greedy, 900, https://codeforces.com/problemset/problem/1879/B

You are given a board of size 𝑛×𝑛 (𝑛 rows and 𝑛 colums) and two arrays of positive integers 𝑎 and 𝑏 of size 𝑛n.

Your task is to place the chips on this board so that the following condition is satisfied for every cell (𝑖,𝑗):

there exists at least one chip in the same column or in the same row as the cell (𝑖,𝑗). I. e. there exists a cell (𝑥,𝑦) such that there is a chip in that cell, and either 𝑥=𝑖 or 𝑦=𝑗 (or both).

The cost of putting a chip in the cell (𝑖,𝑗) is equal to $𝑎_{𝑖} + 𝑏_{𝑗}$ .

For example, for 𝑛=3, 𝑎=[1,4,1] and 𝑏=[3,2,2]. One of the possible chip placements is as follows:

The total cost of that placement is (1+3)+(1+2)+(1+2)=10.

Calculate the minimum possible total cost of putting chips according to the rules above.

Input

The first line contains a single integer $𝑡 (1 \leq 𝑡 \leq 10^{4})$ — the number of test cases.

The first line of each test case contains a single integer $𝑛 (1 \leq 𝑛 \leq 3 \cdot 10^{5})$ .

The second line contains 𝑛n integers $𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑛} (1 \leq 𝑎_{𝑖} \leq 10^{9})$ .

The third line contains 𝑛n integers $𝑏_{1}, 𝑏_{2}, \dots, 𝑏_{𝑛} (1 \leq 𝑏_{𝑖} \leq 10^{9})$ .

The sum of 𝑛 over all test cases doesn't exceed $3 \cdot 10^{5}$ .

Output

For each test case, print a single integer — the minimum possible total cost of putting chips according to the rules.

Example

Input

Output

Note

The first test case of the example is described in the statement.

在一个 n×n 的网格里，设一个点$ (i,j)$的代价为 $a_{i} + b_{j}$ ，要选出一些点，选取的点所在的横行或纵列会被填充，要求：每个点都被填充，选择的点的代价之和最少。

要使每个点都满足，最少的芯片个数应该为 n。要么每一行各有一个芯片，要么每一列各有一个芯片，否则就会有格子影响不到，无法满足规则。那么我们只要把所有芯片都放在代价最小的那一行（列）上，最后比较都放都放在同一行上代价小还是都放在同一列上代价小即可。从数组a中找一个最小的数，分别和b数组相加；从数组b中找一个最小的数，分别和a数组相加。最后取较小者。

python

t = int(input())
for _ in range(t):
    n = int(input())
    *a, = map(int, input().split())
    *b, = map(int, input().split())
    
    min_a = min(a)
    min_b = min(b)
    
    ans1 = sum([min_a + i for i in b])
    ans2 = sum([min_b + i for i in a])
    print(min(ans1, ans2))

1879B. Chips on the Board ​

1879B. Chips on the Board