题目背景

这看起来是经典动态规划题。

但如果你真的这么以为，那就大错特错了！

题目描述

有一个数字三角形：

    1
   1 4
  5 1 4
 1 9 1 9
0 8 1 0 0

你需要完成 $3$ 个操作：

1. 你所熟知的那个 IOI 1994 里典型的数字三角形：从最上方的 $1$ 向下走，每一步可以走到左下方和右下方的点，一直走到最后一行，求经过路径的和的最大值；
2. 从左下方的 $0$ 向右上方走，每一步可以走到右边和右上方的点，一直走到最右侧的一排，求经过路径的和的最大值；
3. 从右下方的 $0$ 向左上方走，每一步可以走到左边和左上方的点，一直走到最左侧的一排，求经过路径的和的最大值。

那么三个问题的步骤和答案如下：

1. $1\to1\to5\to9\to8$，$1+1+5+9+8=24$；
2. $0\to8\to9\to1\to9$，$0+8+9+1+9=27$；
3. $0\to9\to1\to9\to5$，$0+9+1+9+5=24$；

现在，请你编写一个程序，求出任意一个 $n$ 行数字三角形以上的三个路径和。

输入格式

共 $n+1$ 行。

第 $1$ 行，$1$ 个数 $n$；

第 $2\sim n+1$ 行，为数字三角形的每一行。

输出格式

一行，为题意中三条路径上的数字和，用空格分隔输出。

输入输出样例

5
1
1 4
5 1 4
1 9 1 9
0 8 1 0 0

24 27 24

数据范围

对于 $40\%$ 的数据：$0<n\le100$，$0\le 三角形上的数 \le1000$；

对于 $100\%$ 的数据：$0<n\le1000$，$0\le 三角形上的数 \le10000$。