310743: CF1879B. Chips on the Board
Description
You are given a board of size $n \times n$ ($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:
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.
InputThe 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$ ($1 \le n \le 3 \cdot 10^5$).
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).
The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$).
The sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.
OutputFor each test case, print a single integer — the minimum possible total cost of putting chips according to the rules.
ExampleInput4 3 1 4 1 3 2 2 1 4 5 2 4 5 2 3 5 5 2 4 5 3 3 4 2 1 5Output
10 9 13 24Note
The first test case of the example is described in the statement.
Output
你有一个n x n大小的棋盘,以及两个长度为n的正整数数组a和b。你的任务是按照以下条件在棋盘上放置筹码:对于每个单元格(i, j),在同一列或同一行中至少有一个筹码。放置单元格(i, j)中的筹码的成本等于a_i + b_j。计算按照上述规则放置筹码的最小可能总成本。
输入数据格式:
第一行包含一个整数t(1 ≤ t ≤ 10^4)——测试用例的数量。
每个测试用例的第一行包含一个整数n(1 ≤ n ≤ 3 × 10^5)。
第二行包含n个整数a_1, a_2, ..., a_n(1 ≤ a_i ≤ 10^9)。
第三行包含n个整数b_1, b_2, ..., b_n(1 ≤ b_i ≤ 10^9)。
所有测试用例的n之和不超过3 × 10^5。
输出数据格式:
对于每个测试用例,打印一个整数——按照规则放置筹码的最小可能总成本。题目大意: 你有一个n x n大小的棋盘,以及两个长度为n的正整数数组a和b。你的任务是按照以下条件在棋盘上放置筹码:对于每个单元格(i, j),在同一列或同一行中至少有一个筹码。放置单元格(i, j)中的筹码的成本等于a_i + b_j。计算按照上述规则放置筹码的最小可能总成本。 输入数据格式: 第一行包含一个整数t(1 ≤ t ≤ 10^4)——测试用例的数量。 每个测试用例的第一行包含一个整数n(1 ≤ n ≤ 3 × 10^5)。 第二行包含n个整数a_1, a_2, ..., a_n(1 ≤ a_i ≤ 10^9)。 第三行包含n个整数b_1, b_2, ..., b_n(1 ≤ b_i ≤ 10^9)。 所有测试用例的n之和不超过3 × 10^5。 输出数据格式: 对于每个测试用例,打印一个整数——按照规则放置筹码的最小可能总成本。