[AdditionalFile5293.zip](file://AdditionalFile5293.zip?type=additional_file)

#5293. 「PA 2014」Kuglarz

标签: 传统 | 时间限制: 2500 ms | 内存限制: 128 MiB |

题目描述

题目译自 PA 2014 Runda 1 Kuglarz

嘿，伙计们！这小摊有奇迹！我大概是疯了，竟然送钱！

Bitocy 在拜托瓦的集市上以魔术师的身份谋生。

他邀请路人参与一种特殊的游戏。桌子上摆放着 $n$ 个杯子，编号为 $1, 2, \ldots, n$，其中一些杯子下面藏有橡胶小球。如果玩家能准确猜出哪些杯子下面有小球，就能赢得一只大毛绒熊。Bitocy 会向玩家有偿提供线索。以 $c_{ij}$ 拜托格罗什的价格，Bitocy 愿意透露编号为 $i, i+1, \ldots, j$ 的杯子下藏小球数量的奇偶性。

Bajtazar 带着拜托瓦最漂亮的姑娘 Bajtyna 一起来到集市。他非常想为她赢得毛绒熊。同时，他不想冒险在不确定的情况下猜测。他会不断付费获取线索，直到收集到的信息让他能够确信无疑地确定哪些杯子下面有小球。

在了解所有可能线索的价格后，他现在想知道最多需要花费多少钱。更具体地说，他希望知道最小的数字 $k$，使得存在一种询问策略，无论 Bitocy 给出怎样的回答，都能以不超过 $k$ 拜托格罗什的成本定位小球。

输入格式

输入数据的第一行包含一个整数 $n$ $(1 \leq n \leq 2000)$，表示杯子数量。

接下来是询问各区间成本的描述。第 $(i+1)$ $(1 \leq i \leq n)$ 行包含 $n+1-i$ 个整数，表示各个线索的成本。

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

输出格式

输出一个整数，表示采用最优询问策略确定小球位置的最大成本。

样例

输入

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

输出

7