Statement

Basketball is a well known sport that everybody loves it, so does ssw.
One day, ssw assembled $2n$ players. They are told to line up as two teams to practice passing the basketball. For each team, there are $n$ players. They are required to pass the ball to the players of the other team. Because of their different physical ability, they can only pass the ball to the players in a certain range(that depends on themselves). ssw wants to know, with the best strategy, what is the minimum number of the pass that is needed to be made to let the ball passes from the left of two teams to the right(which team to begin with and which team to end with are not important).
As ssw is a member of ACM Association, he decided to write a program to solve that.

Input

There are $T$ testcases.
The first line contains a positive integer $T(1\le T\le 10)$, denoting the amount of testcases.
For each testcase:
The first line of the input contains a positive integer $n(1\le n \le 10000)$, denoting the amount of the basketball players in one team.
The second line of the input contains $n$ positive integer $a_{i}(1\le n \le 100000000)$, denoting the range that player $a_{i}$ could pass through.
The third line of the input contains $n$ positive integer $b_{i}(1\le n \le 100000000)$, denoting the range that player $b_{i}$ could pass through.
It is guarateed that the sum of n will not exceed $100000$.

Output

For each testcase:
You should print the mininum number of the pass in a single line.

Samples

Sample_1

Input

1
10
1 2 3 1 1 1 1 1 1 1
2 2 1 1 1 1 1 1 1 1

Output

6

std

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 1;

int t;
int n;
int a[N], b[N];
int dp[N][2];

int main() {
    scanf("%d", &t);

    while ( t-- ) {
        scanf("%d", &n);
        for ( int i = 1; i <= n; ++i )
            scanf("%d", &a[i]);
        for ( int i = 1; i <= n; ++i )
            scanf("%d", &b[i]);

        memset(dp, 0x3F, sizeof dp);
        dp[1][0] = dp[1][1] = 0;
        for ( int i = 1; i <= n; ++i ) {
            for ( int j = 1; j <= a[i] && i + j <= n; ++j )
                dp[i + j][1] = min(dp[i + j][1], dp[i][0] + 1);
            for ( int j = 1; j <= b[i] && i + j <= n; ++j )
                dp[i + j][0] = min(dp[i + j][0], dp[i][1] + 1);
        }

        printf("%d\n", min(dp[n][0], dp[n][1]));
    }

    return 0;
}

Testcases and datamaker

Game.zip