题目描述

输入一个n，表示要走出迷宫的会经过多少个房间。最开始只有一个房间，接下来每次都可以从三个房间中选择一个进入，当经过n个房间后希蒙就能走出迷宫了，不幸的是，李老师为每个房间都安排了一个阻碍，希蒙会因此花费时间通过此房间，现在需要让希蒙以尽可能最快的方式通过迷宫。快来帮助他计算一下吧

输入格式

一共有n+1行数据

第一行输入一个整数n表示需要通过的房间数

后面的i+1行每行输入2*i-1个整数，表示每个房间需要花费的时间

(i从1到n)

输出格式

输出到达迷宫出口得到的最小值

样例

输入样例

4
5
6  7  8
9  10 11 12 13
14 15 16 17 18 19 20

输出样例

34