9. 好想吃马斯卡彭喵！

Problem I. 好想吃马斯卡彭喵！

小龙面前有 $n$ 个盒子，编号 $1$ 到 $n$。每个盒子中至多放有一个马斯卡彭蛋糕，但小龙并不知道这些蛋糕的具体分布。

小刘可以告诉小龙任意一个连续区间 $[l,r]$ 内蛋糕总数的奇偶性，但每次询问需要支付一定的费用 $w_{l,r}$。

小龙希望确定哪些盒子内有蛋糕，问最少需要支付的总金额是多少。

Input

第一行一个整数 $n$ $(1 \le n \le 2000)$，表示盒子的数量。

接下来 $n$ 行，第 $i$ 行有 $n-i+1$ 个整数，其中第 $j$ 个整数表示询问区间 $[i,i+j-1]$ 的价格 $w_{i,i+j-1}$ $(1 \le w_{i,i+j-1} \le 10^9)$。

Output

输出一个整数，表示最小总金额。

Example

样例输入1

4
1 2 5 6
10 5 6
3 1
9

样例输出1

7

样例输入2

4
1 2 2 6
4 2 3
3 3
4

样例输出2

8

Note

样例1的一种方案如下：

询问 $[1,1]$，花费 $1$，得到奇偶性，确定第 $1$ 个盒子。

询问 $[1,2]$，花费 $2$，结合前一步确定第 $2$ 个盒子。

询问 $[3,3]$，花费 $3$，确定第 $3$ 个盒子。

询问 $[3,4]$，花费 $1$，结合前一步确定第 $4$ 个盒子。

可以证明这是最小花费方案。

样例2的一种方案如下：

询问 $[1,1]$，花费 $1$。

询问 $[1,3]$，花费 $2$。

询问 $[2,4]$，花费 $3$。

询问 $[1,2]$，花费 $2$。

通过这些信息可以唯一确定所有盒子的状态。

来源

郑州轻工业大学“筑梯杯”第十八届程序设计大赛暨省内高校邀请赛 I

数据来源：

1-20：ChenBp

21-30：fanyingzhen