题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点（金字塔第一层）走到底部任意某点结束的所有路径中，路径经过数字的和的最大值。每一步可以走到左下方的点，也可以走到右下方的点。

上图所示数字金字塔，$(1,1)→(2,1)→(3,1)→(4,2)→(5,2)$ 的路径经过数字的和最大。

输入格式

输入文件名：tower.in

第 $1$ 行是要处理的数字金字塔的数量 $T$。

紧接着有 $T$ 组输入。每组第 $1$ 行是一个正整数 $n$ ，表示本组数字金字塔的高度；紧接着有 $n$ 行，第 $i$ 行有 $i$ 个正整数，就是本组数字金字塔第 $i$ 层上的所有数字，相邻数字用一个空格隔开。

输出格式

输出文件名：tower.out

对于每组数字金字塔，找出一条使经过数字的和最大的那条路径（如果有多条符合条件的路径，那么取 最左边 的那条路径）。

输出有 $T*2$ 行。对于输入的每组数字金字塔，有两行输出。

第一行是找到的目标路径经过数字的和，第二行是找到的目标路径依次经过的每个点的坐标 $(x_i,y_i)$，相邻两个坐标用一个空格隔开。

输入输出样例

注意本题要重定向输入输出到指定文件

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

30
(1,1) (2,1) (3,1) (4,2) (5,2)
14
(1,1) (2,1) (3,1) (4,2)

说明/提示

注意本题要重定向输入输出到指定文件

👀️ 对于$100\%$ 的数据，$1 \leq T \leq 100$，$2 \leq n \leq 500$，数字金字塔每层的数字都是不超过 $100$ 的正整数。