题目描述

锋喙鸟的家族是很庞大的，也是峡谷里面一组数量最多的野怪，因为数量较多，所以 $\mathcal{Rubyonly}$ 也不爱刷锋喙鸟，除非给他指一条收益最多的刷锋喙鸟的刷野路线。

现在这些锋喙鸟聚集在了树上，从底层往上数量会越来越多。树共有 $n$ 层，第 $i$ 层有 $i$ 只锋喙鸟，且树的形状呈一个三角形（如图），从上到下相当于从树的底层往上。

图中的一个点表示一只锋喙鸟，每个点上方的数字表示击杀这只锋喙鸟能提供的经验，在刷完一只锋喙鸟后，$\mathcal{Rubyonly}$ 只能选择向左下方或者向右下方接着刷，一直刷到树顶为止。

现在 $\mathcal{Rubyonly}$ 想要知道他从树的最底层往上刷到树顶能够获得的最大经验值是多少。

输入格式

从文件 f6.in 中读入数据。

第 $1$ 行一个整数 $n$。

第 $2\sim n + 1$ 行中，第 $i + 1$ 行有 $i$ 个正整数，表示树上第 $i$ 层中每只锋喙鸟能提供的经验值。

输出格式

输出到文件 f6.out 中。

一行一个整数，表示 $\mathcal{Rubyonly}$ 能够获得的最大经验值。

3
1
2 3
4 6 5

10

数据范围

对于 $10\%$ 的数据，$n = 1$；

对于 $20\%$ 的数据，$n\leq 10$；

对于 $50\%$ 的数据，$n\leq 20$；

对于 $100\%$ 的数据，$1\leq n\leq 10^3$，且保证最后答案不超过 $int$ 范围。