题目描述

给定一个数塔，要求从底层走到顶层。每一步只能从当前结点走到上一层相邻的结点。请找出一条路径，使经过结点的数字之和最大，并输出从塔底到塔顶的行走路径以及最大数字和。

测试数据保证最大路径唯一。

输入格式

第一行输入一个整数 $N$，表示数塔的高度。

接下来 $N$ 行，第 $i$ 行输入 $i$ 个整数，表示数塔第 $i$ 层的数字。

输出格式

第一行输出行走路径，格式为 行号,列号->行号,列号->...，路径顺序为从塔底到塔顶。

第二行输出最大数字和。

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

5,2->4,2->3,1->2,1->1,1
30

数据范围与提示

• $1 \le N \le 100$
• 所有整数均在 $0$ 到 $99$ 之间

可以从塔底向上做动态规划，同时记录每个位置选择的下一步，以便还原最大路径。