题目内容

哨所铺成一块边长为 $w$ 的方阵。西北角 $(1,1)$ 只站着一名哨兵。方阵每个格子 $(r,c)$ 里起初有 $h_{r,c}$ 名密探。

走动只有两条规矩：

• 人还没抵达最南一排、并且下一步仍落在方阵内时，只能朝南一格，或朝东一格。朝南则行号加一、列号不动；朝东则列号加一、行号不动。
• 已经站在最南一排的人，哨兵与密探都不许再挪。

接着双方都要走到不能再走，最终都停在最南一排的某一格：

• 同一格里的密探各自选路，可以连续朝南或朝东，直到被最南一排挡住。
• 哨兵用同样的走法挑一条路，最后也停在最南一排的某一格。

哨兵停住的那一格上有几名密探，这几名就全部被截获。

双方都按对自己最有利的方式选路：

• 密探先全部走完，哨兵再决定停在最南一排的哪一格。
• 哨兵希望截获人数尽量多，因此会去最终人数最多的那一格。
• 密探希望被截获的人数尽量少。他们知道哨兵会挑最挤的格子，于是把路线选成让这个最挤人数变得最小。

问：双方都这样选时，哨兵会截获多少名密探？

输入描述

开头单独给出方阵边长，这个整数记作 $w$（$1 \le w \le 1000$）。

其后还有 $w$ 行。第 $c$ 行有 $w$ 个整数，依次是第 $c$ 列从北到南的人数 $h_{1,c}, h_{2,c}, \ldots, h_{w,c}$（$0 \le h_{r,c} \le 10^9$）。

输出描述

只交出一个整数，也就是双方都选最优路线时，哨兵截获的密探人数。

样例1

输入

3
2 0 1
0 4 0
1 0 2

输出

4

说明

输入按列给出。把方阵按行写开是：北起第一行 $2\ 0\ 1$，第二行 $0\ 4\ 0$，最南一排 $1\ 0\ 2$。

最南一排的 $1$、$0$、$2$ 不能再挪。北侧还能分流的人数按列是 $2$、$4$、$1$。东边两列合起来有 $7$ 人，只能停在东边 $2$ 格里，所以至少有一格达到 $\lceil 7 / 2 \rceil = 4$。一种达得到的停法是：西列北侧 $2$ 人留在本列，该列末格变成 $3$；中间 $4$ 人留在本列，末格变成 $4$；东列末格变成 $3$。峰值就是 $4$。

样例2

输入

2
5 0
1 3

输出

5

说明

按行写开是：北行 $5\ 1$，最南一排 $0\ 3$。东列北侧那 $1$ 人只能留在东列，东列至少是 $3 + 1 = 4$。西列北侧 $5$ 人可以留在西列，也可以走到东列。$5$ 人全留下时，两列是 $5$ 和 $4$；把其中 $1$ 人送到东列，两列是 $4$ 和 $5$。峰值都是 $5$，再压就装不下。