题目描述

你有一个高为 $n$ 的三角形。这个三角形共有 $n$ 行，第 $i$ 行有 $i$ 个正整数。

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

开始时，你在第一行的数字上，每一次你可以选择向它的左下方或右下方行走一步，并获取该位置上的分数。

求出你可以获得的最大分数。

输入格式

输入共 $n+1$ 行。

第一行一个正整数 $n$ 表示三角形的行数。

接下来 $n$ 行，第 $i$ 行 $i$ 个正整数，其中第 $j(1\le j<i)$ 个正整数表示第 $i$ 行第 $j$ 个数字 $a_{ij}$。

输出格式

输出共一行一个正整数，表示最大分数。

样例输入

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

样例输出

30

数据范围

对于全部的数据，$1\leqslant n\leqslant 1000$，$1\leqslant a_{ij}\leqslant 100$。