SUMITR - Sums in a Triangle


Let us consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line etc. Develop a program which will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:

  • on each path the next number is located on the row below, more precisely either directly below or below and one place to the right;
  • the number of rows is strictly positive, but less than 100;
  • all numbers are positive integers between O and 99.

Take care about your fingers, do not use more than 256 bytes of code.

Input

In the first line integer n - the number of test cases (equal to about 1000). Then n test cases follow. Each test case starts with the number of lines which is followed by their content.

Output

For each test case write the determined value in a separate line.

Example

Input:
2
3
1
2 1
1 2 3
4 
1 
1 2 
4 1 2
2 3 1 1 

Output:
5
9
Warning: large Input/Output data, be careful with certain languages

hide comments
baadshah_: 2017-11-30 15:37:47

Wrote whole code in single Line with some optimization.... Finally AC... (253 Bytes) in c++

arjun8115: 2017-10-19 18:20:57

It takes LARGEST POSSIBLE space optimisation...

karthik1997: 2017-08-27 15:50:39

Man , a lot of space optimisations ,took my code to 255b . AC finally :D

scorpion_ajay: 2017-03-11 13:20:18

@kuszi
you are new devil for java users now ;P

nilabja16180: 2017-03-09 15:47:52

250B, AC in ONE GO!
memory constraint is unnecessary!

cake_is_a_lie: 2017-02-21 04:52:07

The author must really hate properly formatted code.

sarthak_8: 2017-02-10 11:34:04

Good question for DP beginners. But the space constraint is unnecessary.

kg93999: 2017-01-20 20:33:53

impossible to do in java :(

prasoonbatham: 2017-01-07 20:14:20

Unnecessary space constraints on file :(

apurvgs: 2016-12-21 17:34:47

waste of time............why the point of 256 bytes

Last edit: 2016-12-21 17:39:06

Added by:kuszi
Date:2004-12-01
Time limit:2s
Source limit:256B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:6-th International Olympiad In Informatics July 3-10. 1994. Stockholm - Sweden, Problem 1