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

Нико играет в игру. Её счёт обозначается целым числом $$$k$$$, которое изначально равно $$$0$$$.

В игре $$$n$$$ ходов. На $$$i$$$-м ходе Нико получает красную карту с целым числом $$$a_i$$$ на ней, а также синюю карту с целым числом $$$b_i$$$ на ней. Она должна выбрать ровно одну из карт и обновить свой счёт в соответствии с её выбором:

  • Если она выбирает красную карту, её счёт становится $$$k - a_i$$$, где $$$k$$$ — это её счёт до хода.
  • Если она выбирает синюю карту, её счёт становится $$$b_i - k$$$, где $$$k$$$ — это её счёт до хода.

После этого наступает следующий ход, или игра заканчивается, если это $$$n$$$-й ход.

Ваша задача — найти максимальный возможный счёт, который Нико может получить в конце игры.

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

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

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

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

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

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

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

Для каждого набора входных данных выведите одно целое число — максимальный возможный счёт, который Нико может получить в конце игры.

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

В первом наборе входных данных одна оптимальная стратегия выглядит следующим образом:

Ход0123
Выбранная карта —СиняяКраснаяКрасная
Счёт$$$0$$$$$$-3 - 0 = -3$$$$$$-3 - (-8) = 5$$$$$$5 - (-1) = 6$$$
Во втором наборе входных данных одна оптимальная стратегия выглядит следующим образом:
Ход012345
Выбранная карта —СиняяСиняяСиняяСиняяКрасная
Счёт$$$0$$$$$$-5$$$$$$8$$$$$$-9$$$$$$13$$$$$$12$$$