题目描述

大黄蜂要从圣堡的圣歌盟地向下移动到深渊

整个地图可以看作是一个 N 层的三角形，其中有若干椅子可供休息。（第 i 层第 j 把椅子表示为 $a_{ij}$）

大黄蜂不想让自己太累所以每次经过椅子都会休息。

然而，想要坐椅子是需要收费的。

具体而言，每次经过椅子都需要缴纳上面所表示的念珠数量。

同时，由于大黄蜂急着前往深渊救出蕾丝，大黄蜂不会走回头路。

求出大黄蜂从圣歌盟地到深渊的最少念珠花费

整个地图可以用下图类比，深渊在最下层，只要抵达最下层就可以抵达深渊救出蕾丝。

例如图中7 -> 3 -> 1 -> 4 -> 2是一条通往深渊的路径

约束条件

• $1 \leq N \leq 1000$
• $1 \leq a_{ij} \leq 10^{9}$
• $1 \leq i \leq N$
• $1 \leq j \leq len(a_i)$
• $a_{ij}$ 为整数。

输入

输入以以下格式从标准输入给出：

$N$

$a_{11}$

$a_{21}$ $a_{22}$

$\vdots$

$a_{N1}$ $a_{N2}$ $\dots$ $a_{NN}$

输出

打印大黄蜂从圣歌盟地向深渊移动时坐椅子的最小花费。

样例

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 

17