C. Robot in a Hallway Educational Codeforces Round 133 (Rated for Div. 2)dp

dp问题

There is a grid, consisting of 22 rows and mm columns. The rows are numbered from 11 to 22 from top to bottom. The columns are numbered from 11 to mm from left to right.

The robot starts in a cell (1,1)(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)(1,1), are locked. Each cell (i,j)(i,j) contains a value ai,jai,j — the moment that this cell gets unlocked. The robot can only move into a cell (i,j)(i,j) if at least ai,jai,j seconds have passed before the move.

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

What is the fastest the robot can achieve that?

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of testcases.

The first line of each testcase contains a single integer mm (2≤m≤2⋅1052≤m≤2⋅105) — the number of columns of the grid.

The ii-th of the next 22 lines contains mm integers ai,1,ai,2,…,ai,mai,1,ai,2,…,ai,m (0≤ai,j≤1090≤ai,j≤109) — the moment of time each cell gets unlocked. a1,1=0a1,1=0. If ai,j=0ai,j=0, then cell (i,j)(i,j) is unlocked from the start.

The sum of mm over all testcases doesn't exceed 2⋅1052⋅105.

Output

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.

Example

input

Copy

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

output

Copy

5
19
17
3

#include 
using namespace std;
const int N=200010;
int a[4][N];
int dp[4][N];
int main()
{
    int t,m,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&m);
        for(i=1;i<=2;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        a[1][1]=-1;
        dp[1][m+1]=dp[2][m+1]=1;
        for(j=m;j>=1;j--)
            for(i=1;i<=2;i++)
                dp[i][j]=max(max(a[i][j]+2*(m-j+1),a[3-i][j]+1),dp[i][j+1]+1);
        int ans=5e9;
        int num=0;
        for(j=1;j<=m;j++)
        {
            int k=3-(j%2+1);
            ans=min(ans,max(num,dp[k][j]));
            num=max(num,a[k][j]+2*(m-j+1));
            num=max(num,a[3-k][j]+2*(m-j+1)-1);
        }
        cout<
    }
    return 0; 
}