The Code Game

All submissions for this problem are available.
Akhilesh and Ayush start playing a game. The game consists of placing 2*N coins in a row.
The denominations of coins can be anything from 0(zero) to 200.
In each turn, the player can pick either the leftmost coin or the rightmost coin.
The strategy is simple. At the end the one with more value of coins wins.
Akhilesh has the first turn. He being a programmer thinks of automating the process in order to beat his friend Ayush.
He makes a program that will always win if Akhilesh has the first turn, no matter what Ayush does.
You are in place of Akhilesh and have to build a similar program.
Input
The first line consists of 'T' the number of test cases.'T' games follow.
Each game inputs N (half the number of coins) which are followed by 2*N values denoting the denominations of the coins.
The denomination values are separated by a space.
Output
Output one line per test case  the maximum value of coins Akhilesh has.
Sample Input
2
4
12 45 10 18 32 86 42 102
2
12 19 14 15
Sample Output
251
34
Constraints
1 <= T <= 500
1 <= N <= 100
Author:  csaapogee 
Tags  csaapogee 
Date Added:  15032013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, GO, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 