新数字三角形问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

给定一个由n(<=100)行数字组成的数字三角形如下所示。设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。7

 

3 8

8 1 0

2 7 4 1

4 5 2 6 1

 

对于给定的由n行数字组成的数字三角形,计算从三角形的顶至底的路径经过的数字和的最大值,并输出这个路径的完整坐标。

 

Input

多组输入
每组数据第一行输入一个n。
接下来的n行,对于第 i(1 --> n) 行每行有 i 个不超过200的正整数
保证对于这n行数据,每行的数字不会重复,如果在某一行的最大值相同了,优先输出靠近左边(j较小)的坐标。

Output

 对于每组数据输入一个最大值,占一行。
接下来的n行,每行两个整数,代表你得到这个最大值所走的路径坐标。

Sample Input

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

Sample Output

30
5 2
4 2
3 1
2 1
1 1

Hint

Source

2015级《程序设计基础II》计科软件通信期末上机考试2 - by Casithy