← Home
write a go solution for Description:
You are given a board of size nxn (n rows and n colums) and two arrays of positive integers a and b of size n.

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

- there exists at least one chip in the same column or in the same row as the cell (i,j). I. e. there exists a cell (x,y) such that there is a chip in that cell, and either x=i or y=j (or both).

The cost of putting a chip in the cell (i,j) is equal to a_i+b_j.

For example, for n=3, a=[1,4,1] and b=[3,2,2]. One of the possible chip placements is as follows:

White squares are empty

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 Format:
The first line contains a single integer t (1<=t<=10^4) — the number of test cases.

The first line of each test case contains a single integer n (1<=n<=3*10^5).

The second line contains n integers a_1,a_2,...,a_n (1<=a_i<=10^9).

The third line contains n integers b_1,b_2,...,b_n (1<=b_i<=10^9).

The sum of n over all test cases doesn't exceed 3*10^5.

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

Note:
The first test case of the example is described in the statement.. Output only the code with no comments, explanation, or additional text.