#656. 地宫勇者小码君

地宫勇者小码君

题目描述

勇者小码君为了拯救整个被蜘蛛女皇所恐怖统治的阿拉德大陆,来到了蜘蛛女皇的地下行宫讨伐蜘蛛女皇,蜘蛛女皇在地下行宫的最深处。地宫一共深n+1层,前n层第i层有i处通往下一层的入口,每个入口处都有小兵把守,我们需要尽可能的节省勇者小码君的体力,让他在找到蜘蛛女皇前碰到的小兵的数量尽可能少,小码君只能沿着红色的路线(左下或者右下)向下一层探索,蜘蛛女皇的5层地宫图如下。 WObEcV.png

每个正方形方块代表一个通往下一层的据点,里面的数字代表小兵的数量,解决掉每一个小兵所耗费的体力为1,只能沿着红色路径(左下或者右下)向下一层探索,输出津津在找到蜘蛛女皇时所耗费的最小体力。

输入格式

第1行输入一个正整数n,表达到达最底层之前的地宫层数

接下来输入n行数据

第1行输入1个数据表示据点的小兵数量

第2行输入2个数据表示据点的小兵数量

……………………

第n行输入n个数据表示据点的小兵数量

输出格式

一个整数n,表示津津在找到蜘蛛女皇时所耗费的最小体力。

样例

样例输入

4
6
5 8
3 1 9
6 2 4 3

样例输出

14