Заданы два массива целых чисел \(a\) и \(b\) длины \(n\).
Вы можете выполнить следующую операцию любое количество раз (возможно ноль): поменять местами \(a_i\) и \(b_i\).
Пусть \(f(c)\) – наибольшая сумма среди всех непрерывных подотрезков массива \(c\) (включая пустой подотрезок, сумма которого равна \(0\)).
Ваша задача — посчитать максимально возможное значение \(f(a) + f(b)\), используя вышеупомянутую операцию любое количество раз.
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\)).
Третья строка содержит \(n\) целых чисел \(b_1, b_2, \dots, b_n\) (\(-10^9 \le b_i \le 10^9\)).
Сумма \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).
Для каждого набора входных данных выведите одно целое число — максимально возможное значение \(f(a) + f(b)\), используя вышеупомянутую операцию любое количество раз.
3 3 2 -1 3 -4 0 1 6 4 2 -6 1 6 -4 -6 -2 -3 7 -3 2 2 -2 -5 0 -1
6 21 0
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач