Background

Description

计算数字三角形的每层最大累加值并输出

Format

Input

Output

Samples

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

30
23 21
20 13 10
7 12 10 10
4 5 2 6 5

Limitation

1s, 1024KiB for each test case.