运送情报
Description:
日军的集中大量优势兵力包围我根据地，我军奋力抵抗，双方陷入胶着状态，并且与外部失去了联系。师部决定，派出一支精干力量实施突围和外部取得联系，运送情报。这就需要作为指挥官的你的指挥。
根据前期侦察，你发现突围需要从内到外突破N道防线，编号从1到N，第i条防线有i个据点，编号从1到i，每个据点有若干单位的情报。由于敌人的破坏和节省时间，从第i条防线的第j号据点你可以且仅可以到第i+1条防线的第J号据点或第J+1号据点。问你可以送出的最大单位情报。最开始你在1号防线。
Input:
一个N数（1<N<1000），表示防线的数量。接下来N行。第i行有i（1<=i<=N）个数a0-ai以空格隔开，表示该据点的情报单位数。(0<ai<10000)
Output:
可送出去的最大情报单位
Sample Input:
4 1 2 3 4 5 6 7 8 9 10
Sample Output:
20
Source:
Submit