题目描述

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

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

输入格式

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

接下来输入n行数据

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

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

……………………

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

输出格式

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

样例

样例输入

4
6
5 8
3 1 9
6 2 4 3

样例输出

14