嘿，伙计们！快来看这儿的奇迹！我一定是疯了，正在大把撒钱！—— Bitocy 在 Bajtowa 的集市上靠当魔术师谋生。

他邀请路人参与一个独特的游戏。桌子上排成一排摆放着 $n$ 个杯子，编号为 $1, 2, \dots, n$，其中一些杯子下藏着橡胶球。如果玩家能准确猜出哪些杯子下有球，就能赢得一只巨大的毛绒泰迪熊。Bitocy 收费提供提示。只要支付 $c_{ij}$ 个 Bajtogrosz（货币单位），Bitocy 就愿意透露编号从 $i$ 到 $j$ 的杯子下藏球数量的奇偶性。

Bajtazar 和 Bajtowa 最漂亮的姑娘 Bajtyna 一起来到了集市。他非常想为她赢得那只泰迪熊。他不想在没有把握的情况下胡乱猜测而丢脸。他打算一直购买提示，直到收集到的信息足以让他确定哪些杯子下藏有球。

已知所有可能提示的价格，他现在想知道，为了确定球的位置，他最多需要花费多少钱。更准确地说，他想知道最小的数字 $k$，使得存在一种提问策略，无论 Bitocy 的回答如何，都能以不超过 $k$ 个 Bajtogrosz 的总成本确定球的位置。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 2000$)，表示杯子的数量。接下来是关于查询各个区间成本的描述。输入的第 $i+1$ 行（对于 $1 \le i \le n$）包含 $n+1-i$ 个整数，表示各个提示的成本。

查询区间从第 $i$ 个杯子到第 $j$ 个杯子（包含 $i$ 和 $j$）的成本 $c_{ij}$ ($1 \le i \le j \le n, 1 \le c_{ij} \le 10^9$) 在输入中作为第 $i+1$ 行的第 $(j+1-i)$ 个数字出现。

输出格式

你的程序应该输出一个整数，表示在最优提问策略下，确定球的位置所需的最大成本。

样例

输入 1

5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5

输出 1

7