470. [NOI 2010]海拔

【问题描述】

YT 市是一个规划良好的城市，城市被东西向和南北向的主干道划分为 $n \times n$ 个区域。简单起见，可以将YT市看作 一个正方形，每一个区域也可看作一个正方形。从而，YT 城市中包括 $(n + 1) \times (n + 1)$ 个交叉路口和 $2n \times (n + 1)$ 条双向道路（简称道路），每条双向 道路连接主干道上两个相邻的交叉路口。下图为一张 YT 市的地图（$n = 2$），城市被划分为 $2 \times 2$ 个区域，包括 $3 \times 3$ 个交叉路口和 $12$ 条双向道路。

小Z 作为该市的市长，他根据统计信息得到了每天上班高峰期间 YT 市每条道路两个方向的人流量，即在高峰期间沿 着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值，YT 市市民认为爬坡是一件非常累的事情，每向上爬 $h$ 的高度，就需要消耗 $h$ 的体力。如果 是下坡的话，则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为 $h$（注意 $h$ 可能是负数），那么一个人经过这段路所消耗的体力是 $\max\{0, h\}$（这里 $\max\{a, b\}$ 表示取 $a, b$ 两个值中的较大值）。

小Z 还测量得到这个城市西北角的交叉路口海拔为 $0$，东南角的交叉路口海拔为 $1$（如上图所示），但其它交叉路口的海拔高度都无法得知。小Z 想知道在最理想的情况下（即你可以任意假设其他路口的海拔高度），每天上班高峰期间所有人爬坡消耗的总体力和的最小值。

【输入格式】

第一行包含一个整数 $n$，含义如上文所示。

接下来 $4n(n + 1)$ 行，每行包含一个非负整数分别表示每一条道路每一个方向的人流量信息。输入顺序：$n(n + 1)$ 个数表示所有从西到东方向的人流量，然后 $n(n + 1)$ 个数表示所有从北到南方向的人流量，$n(n + 1)$ 个数表示所有从东到西方向的人流量，最后是 $n(n + 1)$ 个数表示所有从南到北方向的人流量。对于每一个方向，输入顺序按照起点由北向南，若南北方向相同时由西到东的顺序给出（参见样例输入）。

【输出格式】

仅包含一个数，表示在最理想情况下每天上班高峰期间所有人爬坡所消耗的总体力和（即总体力和的最小值），结果四舍五入到整数。

【样例输入】

1
1
2
3
4
5
6
7
8

【样例输出】

3

【样例说明】

样例数据见下图。

最理想情况下所有点的海拔如上图所示。

【数据规模】

对于 $20\%$ 的数据：$n \le 3$；

对于 $50\%$ 的数据：$n \le 15$；

对于 $80\%$的数据：$n \le 40$；

对于 $100\%$ 的数据：$1 \le n \le 500$，$0 \le 流量 \le 1,000,000$ 且所有流量均为整数。

【提示】

海拔高度不一定是整数。

大样例