SUMTRIAN - Sums in a Triangle (tutorial)


This is problem SUMITR without strict source limit.

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.

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
kamran siddique: 2015-04-21 18:46:31

50th AC :)

sri: 2015-03-25 08:10:46

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; what does this mean

rick: 2014-06-25 21:26:28

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;

I DON'T GET THIS STATEMENT .. EXPLAIN ?

reggaeguitar: 2013-02-27 02:21:30

Check out problem number 18 on projecteuler.net, it is the exact same, just one test case

Vaibhav Jain: 2011-08-01 00:16:53

I am continuously getting an NZEC error with my java program for this problem. I have tested it with other editors and it runs fine. Can anybody please tell me what could be the cause?

Piotr KÄ…kol: 2010-07-24 17:33:10

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.

Edit: The record was beaten by Jander in Perl to 88 chars and in Ruby by Konstantin to 90 chars.

Last edit: 2011-05-12 15:55:32

Added by:kuszi
Date:2004-11-10
Time limit:0.314s
Source limit:5000B
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