CF1716C.Robot in a Hallway

There is a grid, consisting of $2$ rows and $m$ columns. The rows are numbered from $1$ to $2$ from top to bottom. The columns are numbered from $1$ to $m$ from left to right.

The robot starts in a cell $(1, 1)$. In one second, it can perform either of two actions:

• move into a cell adjacent by a side: up, right, down or left;
• remain in the same cell.

The robot is not allowed to move outside the grid.

Initially, all cells, except for the cell $(1, 1)$, are locked. Each cell $(i, j)$ contains a value $a_{i,j}$ — the moment that this cell gets unlocked. The robot can only move into a cell $(i, j)$ if at least $a_{i,j}$ seconds have passed before the move.

The robot should visit all cells without entering any cell twice or more (cell $(1, 1)$ is considered entered at the start). It can finish in any cell.

What is the fastest the robot can achieve that?

有一个由 $2$ 行 $m$ 列组成的网格。行从上到下编号为 $1$ 到 $2$，列从左到右编号为 $1$ 到 $m$。

机器人起始于单元格 $(1, 1)$。每秒钟，它可以执行以下两种操作之一：

• 移动到一个与当前单元格边相邻的单元格：上、右、下或左；
• 停留在当前单元格中。

机器人不允许移出网格边界。

初始时，除单元格 $(1, 1)$ 外，所有单元格均被锁定。每个单元格 $(i, j)$ 包含一个值 $a_{i,j}$ —— 表示该单元格在第 $a_{i,j}$ 秒解锁（即在该时刻或之后才可进入）。机器人仅当移动发生前已过去至少 $a_{i,j}$ 秒时，才能进入单元格 $(i, j)$。

机器人需访问所有单元格，且不得重复进入任一单元格（起始时进入 $(1, 1)$ 视为已访问一次）。它可在任意单元格结束行程。

机器人完成该任务所需的最短时间是多少？

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $m$ ($2 \le m \le 2 \cdot 10^5$) — the number of columns of the grid.

The $i$-th of the next $2$ lines contains $m$ integers $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($0 \le a_{i,j} \le 10^9$) — the moment of time each cell gets unlocked. $a_{1,1} = 0$. If $a_{i,j} = 0$, then cell $(i, j)$ is unlocked from the start.

The sum of $m$ over all testcases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $m$（$2 \le m \le 2 \cdot 10^5$）—— 网格的列数。

接下来 $2$ 行中的第 $i$ 行包含 $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$。

For each testcase, print a single integer — the minimum amount of seconds that the robot can take to visit all cells without entering any cell twice or more.

对于每个测试用例，输出一个整数——机器人访问所有格子（不重复进入任一格子）所需的最少秒数。