ACM International Collegiate Programming Contest, Asia-Amritapuri Site, 2011
Problem C: The Way to the Sorcerer's Stone
Harry Potter has discovered that the Sorcerer's Stone of Immortality is hidden in a dungeon.  Having beaten the three-headed dog to get to the dungeon, Harry discovers to his dismay that the stone is stored at the end of a long crooked corridor with N-1 bends. At each bend in the corridor (and at the start) is either a Hungarian Horntail dragon that our intrepid hero has to defeat, or a flask of magic potion that his teacher Snape has left for him.  A dragon at junction 'i' takes away |S[i]| strength points from him, and a potion at junction 'i' increases Harry's strength by S[i].  If his strength drops to  0 or less, Harry dies, and no magical  stone can revive him.

Note that Harry could be faced with a corridor having no bends (N=1) -- just one single straight section with a flask or a dragon at the start.

Harry has used magic before entering the corridor to determine which bends contain what, but lacks the basic simple mathematical skill to determine what minimum strength he needs to emerge from the corridor alive. Can you help him again with your compooter-thingy?
Input (STDIN):
The first line contains the number of test cases T. T cases follow. Each test case consists of  N in the first line followed by N space separated integers on the next line. If the ith value is negative, it indicates that the ith segment has a dragon, otherwise it indicates a magic potion.
Output (STDOUT):
Output T lines, one for each case containing the required answer for the corresponding case.
Constraints:
1 <= T <= 100
1 <= N <= 100
-100 <= S[i] <= 100
Time limit: 2 seconds
Sample Input:Corridor
3
3
0 0 -1
3
-2 -3 -4
4
2 -2 3 -3
Sample Output:
2
10
1