160. Commandos

Problem Statement:
A commando is a soldier of an elite light infantry often specializing in amphibious landings, abseiling or parachuting.
This time our Commando unit wants to free as many hostages as it could from a hotel in Byteland, This hotel contains 10 identical floors numbered from 1 to 10 each one is a suite of 10 by 10 symmetric square rooms, our unit can move from a room (F,Y,X) to the room right next to it (F,Y,X+1) or front next to it (F,Y+1,X) and it can also use the cooling system to move to the room underneath it (F-1,Y,X).
Knowing that our unit parachuted successfully in room (1, 1) in floor 10 with a map of hostages locations try to calculate the maximum possible hostages they could save.

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 <= T <= 100).
Followed by the test cases, each test case contains a number N (1 <= N <= 1000) representing the number of lines that follows.
Each line contains 4 space separated integers (1 <= F, Y, X, H <= 10) means in the floor number F room (Y, X) there are H hostages.

Output Format:
For each test case, print on a single line, a single number representing the maximum possible hostages that they could save.

Sample Input:
2 3 10 5 5 1 10 5 9 5 10 9 5 9 3 1 5 5 1 5 5 9 5 5 9 5 8

Sample Output:
10 8

 Added by: feras_kassar Added at: 2014-05-19 20:19:50 UTC Time Limit: 2 seconds Partial score: No Source: Tishreen-CPC 2014