SPOJ.com - Problem SUMITR

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

Submit solution!

hide comments

< Previous 1 2 3 4 Next >

	Abhay: 2015-04-10 09:42:15 My submission got accepted in challenge mode but I am getting WA here. Can someone help me? Edit: It got accepted now. I got 3 WAs for the same answer and then it got accepted without any changes... -_- Last edit: 2015-04-10 09:46:17
	Mottakin Chowdhury: 2015-04-04 12:12:30 ŕŚŕŚžŕŚŕŚŚŕŚžŕŚ ŕŚŕŚžŕŚŽŕ§ŕŚ¨ŕŚžŕŚ? -_______-
	Fz: 2015-03-12 10:09:23 what is their aim to set code size limit to 256B? such a small size.. people end up in writing everything in the same line, is that they want? or there is really something else behind this ? please explain this
	Mitch Schwartz: 2013-06-19 05:55:07 @Aniket Kumar: Try saving your C solution to a file; make sure there are no '\r' characters if you are on Windows; and use the "Browse..." button rather than copying and pasting into the edit box. As for Python timing, I suppose Piotr Kąkol made his own test data as he didn't have access to Łukasz Kuszner's data, making the timings somewhat different. Edit: Or, reading the comments, I think Piotr probably made his test data easier intentionally with respect to the time limit to encourage shorter solutions in slower languages. Last edit: 2013-06-19 05:57:18
	Aniket Kumar: 2013-06-18 17:46:59 the same C code is giving 255 bytes in TRI_SUMS (challenge) but here it says too long solution ... Similary the python code ID:9505617 runs in 0.16 sec on TRI_SUMS bt here I get TLE... Somebody please explain to me !!! Last edit: 2013-06-18 17:49:41
	Dominique VAILLANT: 2013-03-10 18:08:18 After removing more bytes my code is no more rejected. I suppose SPOJ editor adds CR to LF... (edit) You can try "choose a file" instead "insert code" : a difference is possible. (edit) Thanks for the suggestion. Last edit: 2013-03-11 02:19:13
	Dominique VAILLANT: 2013-03-10 17:42:37 My code is within the limit but I get an error message: 'Your solution is too long for this problem, the limit is 256 bytes!' Issuing: wc -c sumitr.rb I get: 253 sumitr.rb
	Piotr KÄ…kol: 2011-01-21 17:01:30 @spoofer - There are different tests. BTW, in TRI_SUMS the record is now 89 chars in Perl (in Ruby it's now 90). Edit: Jander has beaten the record to 88 chars. Last edit: 2011-05-12 15:53:33
	Piotr KÄ…kol: 2010-07-24 17:31:15 The same task without limit: TRI_SUMS. But the shorter is Your code, the more points You get. For now the record is 92 characters in Ruby. Last edit: 2010-07-24 17:31:58
	numerix: 2009-06-04 13:21:24 If you submit a solution using copy&paste each EOL seems to be counted as 2 bytes. If you submit it as file that problem doesn't occur.

Submit solution!

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