Description

下图显示了一个数字三角形。每一步都可以向左斜下方走或向右斜下方走，计算从顶到底某条路线上经过的数字的最大和。

Format

第 $1$ 行包含一个整数 $n$ $（$ $1$ $<$ $n$ $≤$ $1$ $0$ $0$ $）$ ，表示三角形的行数。下面的 $n$ 行描述了三角形的数据。三角形中的所有整数都为 $0$ ～ $9$ $9$ 。

输出从顶到底某条路线上经过的数字的最大和。