There is a grid of $$$n \times n$$$ rooms. Rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and columns are numbered from $$$1$$$ to $$$n$$$ from left to right. Room $$$(i,j)$$$ lies in row $$$i$$$ and column $$$j$$$.
There are $$$2n$$$ fans. For each row $$$i$$$, there is a row fan that cools every room in row $$$i$$$ when it is switched on. Switching on this fan costs $$$r_i$$$. For each column $$$j$$$, there is a column fan that cools every room in column $$$j$$$ when it is switched on. Switching on this fan costs $$$c_j$$$.
You may switch on any subset of the fans, paying the sum of their costs. A room is cooled if at least one of its row fan and its column fan is switched on.
Yazan starts in room $$$(1,1)$$$ and wants to reach room $$$(n,n)$$$. In one move, he may go to a room that shares a side with his current room. Every room in his path, including $$$(1,1)$$$ and $$$(n,n)$$$, must be cooled.
Find the minimum total cost of switching on fans so that such a path exists.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of rows and columns.
The second line of each test case contains $$$n$$$ integers $$$r_1,r_2,\ldots,r_n$$$ ($$$1 \le r_i \le 10^9$$$) — the costs of the row fans.
The third line of each test case contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ ($$$1 \le c_i \le 10^9$$$) — the costs of the column fans.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output one integer — the minimum total cost required to create a cooled path from $$$(1,1)$$$ to $$$(n,n)$$$.
3 3 1 100 100 100 100 1 3 3 100 4 100 2 100 3 100 2 100 3 100 4
2 9 9
In the first sample, switching on the fan of row $$$1$$$ and the fan of column $$$3$$$ costs $$$1+1=2$$$. The diagram in the statement shows the cooled rooms and one possible path from $$$(1,1)$$$ to $$$(3,3)$$$.
