Alice and Bob are playing a game. There are two piles of cards. There are N cards in each pile, and each card has a score. They take turns to pick up the top or bottom card from either pile, and the score of the card will be added to his total score. Alice and Bob are both clever enough, and will pick up cards to get as many scores as possible. Do you know how many scores can Alice get if he picks up first?

Input

The first line contains an integer T (T≤100), indicating the number of cases. 
Each case contains 3 lines. The first line is the N (N≤20). The second line contains N integer a i (1≤a i≤10000). The third line contains N integer b i (1≤bi≤10000).

Output

For each case, output an integer, indicating the most score Alice can get.

Sample Input

2 
 
1 
23 
53 
 
3 
10 100 20 
2 4 3

Sample Output

53 
105

题意：有两堆卡牌，每堆都为N张卡牌，每张卡牌有一定的分数，有A，B两个人，他们只能从这两堆中的顶部或者底部抽出一张牌，并且拥有该分数，问当A先手时，他能获得的最大分数是多少。

题解：对抗搜索，菜鸡我第一次写对抗搜索，代码中 l1——r1为第一堆剩下的卡牌，l2——r2为第二堆剩下的卡牌。要想分数最大，他能获得的最大分数 = cur（总分数）- 上一步中另一个人获得的最大分数，因为两个人都足够聪明~~，详细看代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAX = 22;
int val1[MAX],val2[MAX];
int dp[MAX][MAX][MAX][MAX];
int n,sum;
int dfs(int l1,int r1,int l2,int r2,int cur){
	if(l1>r1&&l2>r2) return dp[l1][r1][l2][r2];//不加超时对应return
	if(dp[l1][r1][l2][r2]!=0) return dp[l1][r1][l2][r2];//不加超时对应return
	int cmp=0;
	if(l1<=r1){
		cmp=max(cmp,cur-dfs(l1+1,r1,l2,r2,cur-val1[l1]));
		cmp=max(cmp,cur-dfs(l1,r1-1,l2,r2,cur-val1[r1]));
	}
	if(l2<=r2){
		cmp=max(cmp,cur-dfs(l1,r1,l2+1,r2,cur-val2[l2]));
		cmp=max(cmp,cur-dfs(l1,r1,l2,r2-1,cur-val2[r2]));
	}
	return dp[l1][r1][l2][r2]=cmp;//要加上 “dp[l1][r1][l2][r2]=”cmp，要不然超时
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		sum=0;//求总分的变量
		for (int i = 1; i <= n;i++){
			scanf("%d",&val1[i]);
			sum+=val1[i];
		}
		for (int i = 1; i <= n;i++){
			scanf("%d",&val2[i]);
			sum+=val2[i];
		}
		memset(dp,0,sizeof(dp));//别忘记初始化
		printf("%d\n",dfs(1,n,1,n,sum));
	}
	return 0;
}