P2046 [NOI2010] 海拔

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

无

无

 ### 数据范围 - 对于 $20\%$ 的数据：$n \leq 3$； - 对于 $50\%$ 的数据：$n \leq 15$； - 对于 $80\%$ 的数据：$n \leq 40$； - 对于 $100\%$ 的数据：$1 \leq n \leq 500$，$0 \leq \text{流量} \leq 10^6$ 且所有流量均为整数。