B. Это шедевр!
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть два массива положительных целых чисел $$$a$$$ и $$$b$$$, оба длины $$$n$$$. Вы можете выполнять следующую операцию любое количество раз:

  • выбрать целое число $$$i$$$ ($$$1 \le i \le n$$$) и поменять местами $$$a_i$$$ и $$$b_i$$$.

Определите максимальное значение выражения $$$\max(a) + \sum^{n}_{i = 1}{b_i}$$$, которого можно достичь, если выполнять операции оптимально.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину массивов $$$a$$$ и $$$b$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_{n}$$$ ($$$1 \le a_i \le 10^9$$$).

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_{n}$$$ ($$$1 \le b_i \le 10^9$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите максимальное возможное значение выражения $$$\max(a) + \sum^{n}_{i = 1}{b_i}$$$.

Пример
Входные данные
4
1
2
1
1
1
2
3
1 2 3
4 5 6
4
2 3 6 7
1 4 5 8
Выходные данные
3
3
18
27
Примечание

Пример 3: Обмены не требуются, поэтому ответ равен $$$\max([1, 2, 3]) + 4 + 5 + 6 = 3 + 15 = 18$$$. Можно доказать, что этот вариант является оптимальным.

Пример 4: Максимума можно достичь, если поменять местами элементы на позициях $$$1$$$, $$$3$$$ и $$$4$$$. В результате мы получим:

  • $$$a = [1, 3, 5, 8]$$$
  • $$$b = [2, 4, 6, 7]$$$
Это дает ответ $$$\max([1, 3, 5, 8]) + 2 + 4 + 6 + 7 = 8 + 19 = 27$$$. Можно доказать, что этот вариант является оптимальным.