C. Робот в коридоре
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано поле, состоящее из $$$2$$$ строк и $$$m$$$ столбцов. Строки занумерованы от $$$1$$$ до $$$2$$$ сверху вниз. Столбцы занумерована от $$$1$$$ до $$$m$$$ слева направо.

Робот начинает в клетке $$$(1, 1)$$$. За одну секунду он может проделать любое из двух действий:

  • перейти в соседнюю по стороне клетку: наверх, направо, вниз или налево;
  • остаться в той же клетке.

Роботу запрещено выходить за пределы поля.

Изначально все клетки, кроме клетки $$$(1, 1)$$$ заблокированы. Каждая клетка $$$(i, j)$$$ содержит значение $$$a_{i,j}$$$ — момент, когда данная клетка будет разблокирована. Робот может перейти в клетку $$$(i, j)$$$, если до начала хода прошло хотя бы $$$a_{i,j}$$$ секунд.

Робот должен посетить все клетки, не входя ни в какую клетку дважды или больше (считается, что робот вошел в клетку $$$(1, 1)$$$ на старте). Он может закончить в любой клетке.

Какое минимальное время у него это может занять?

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

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

В первой строке каждого набора записано одно целое число $$$m$$$ ($$$2 \le m \le 2 \cdot 10^5$$$) — количество столбцов поля.

В $$$i$$$-й из следующих $$$2$$$ строк записаны $$$m$$$ целых чисел $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$0 \le a_{i,j} \le 10^9$$$) — момент времени, в который каждая клетка будет разблокирована. $$$a_{1,1} = 0$$$. Если $$$a_{i,j} = 0$$$, то клетка $$$(i, j)$$$ разблокирована с самого начала.

Сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
4
3
0 0 1
4 3 2
5
0 4 8 12 16
2 6 10 14 18
4
0 10 10 10
10 10 10 10
2
0 0
0 0
Выходные данные
5
19
17
3