313005 - 寻找剑神

传说中的剑神居住在山顶，山是环形的，有n层，以一个n行的数字三角形来表示，依次编号为1~n。其中第i行有i个数字，位置依次记为(i,1),(i,2),\cdots,(i,i)，表示该行有i个位置，数字代表走到这个位置需要花费的时间。

现在小光从第n层的第一个位置即(n,1)出发，每一次他都可以向左、右、左上、右上四个方向移动，直到找到剑神的居住处即(1,1)结束，试求在不重复经过任何位置的情形下，路过的所有位置（包括顶点）所花费的时间最少。

第1行有一个数n(2\leq n\leq10^3)，表示山的高度。

从第2行至第n＋1行，第i＋1行有i个数，每个数表示晴天小猪在这一段山路上需要爬的时间。

输出一个数，即所需要的最短时间。