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
pradeep_7: 2020-07-18 10:13:56

Wrote Whole code in a single line(to pass 256bytes) except header file Got A.C.

horro: 2020-06-12 23:12:28

Finally, AC in one go!! after too much struggle to optimise code ..bottom up+i/p array use to store result>> (251Bytes)

Thotsaphon Thanatipanonda: 2020-06-11 11:57:58

Finally I can solve with Java. After waiting for many years until Java 10 release. Yeah!!

Last edit: 2020-06-11 11:59:49
tarunluthra: 2020-04-26 18:35:39

253 bytes. C++. Took a lot of time. Better to solve https://www.spoj.com/problems/SUMTRIAN/ first since its the same problem.

Last edit: 2020-04-26 18:36:03
raipavitra: 2020-02-04 07:27:26

bottom up
and not space for input

xariniov9: 2019-06-19 13:58:21

225B

Last edit: 2019-06-19 14:06:56
adist98: 2019-06-12 13:52:41

What is the point of such a low file size constraint?

Sergey Ushakov: 2018-08-10 16:57:49

Something wrong with that problem. I've solved the TRI_SUMS problem and got AC.
The same code in this problem gives me WA. Could you explain?

AC:
https://gyazo.com/cb09d0d348b9031c4c86997bc50a39ed

WA:
https://gyazo.com/3485a92266b7845694f1edc660dfdf7b

adityad1998: 2018-06-30 11:34:22

Basic DP problem with useless space constraint.
Took 6 attemps to get AC

madhur4127: 2018-03-23 09:57:14

python tutorial problem (229B) :D

Last edit: 2018-03-23 09:57:37

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