数字三角形3

【题目描述】

现有一个数字三角形，从顶点遍历到底层，且可以把遍历过的任何一个数重复累加一边，询问其权值之和最大是多少。

【输入描述】

第一行输入一个数N(N <= 1000)，表示数字三角形的层数；

接下来n行，每行输入若干个数，表示各个节点的权值。

【输出描述】

输出一个数，表示答案。

【样例输入】

5

1

1 3

1 1 3

1 1 1 3

7 1 1 1 3

【样例输出】

18