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 0 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
true_coder: 2016-12-18 00:54:15

Wow! the space thing is tougher than problem, itself...lol

testing java: 2016-12-08 02:21:18

what is the point of such source code limit? as a challenge problem it would be fine, here only made me frustrated (as I wanted to write in java). Btw, anyone with < 320 LOC in java?

ashishranjan28: 2016-10-29 12:16:17

lol...

i think setter has space problem...

Last edit: 2016-11-01 15:21:47
umohan: 2016-08-26 20:28:27

no submission in java

nonushikhar: 2016-05-28 10:38:28

this is good XD

Last edit: 2016-05-28 12:02:48
Akash Shinde: 2016-01-22 18:01:32

What's the point of 256 B?
just to writer everything in one line?

CounterNormalize: 2016-01-16 13:42:18

Finally AC!!! phewwww

Divyansh Shukla: 2015-11-10 18:17:06

Code size restriction of 256B is really wrong.

Akshay Damle: 2015-10-17 00:27:23

AC in 1st go :) A little bit of code golf in Python after a very long time.. was fun :D

kuszi: 2015-08-29 16:56:28

@Fz Just a kind of a puzzle. You will find more like this here: http://www.spoj.com/SHORTEN/.

Last edit: 2015-08-29 17:01:51

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