Description:


现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,
而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:

左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路
1:(x,y)<==>(x+1,y)
2:(x,y)<==>(x,y+1)
3:(x,y)<==>(x+1,y+1)
道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的. 左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角(1,1)的窝里,现在它们要跑到右下解(N,M)的窝中去,狼王开始伏击这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为K,狼王需要安排同样数量的K只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.

Input:


第一行为N,M.表示网格的大小,N,M均小于等于1000.
接下来分三部分
第一部分共N行,每行M-1个数,表示横向道路的权值.
第二部分共N-1行,每行M个数,表示纵向道路的权值.
第三部分共N-1行,每行M-1个数,表示斜向道路的权值.
输入文件保证不超过10M

Output:


输出一个整数,表示参与伏击的狼的最小数量.

Sample Input:


Sample Output:


题解:


这是一道经典题。
根据题意,我们如果把图分成了两个分别包含(1, 1)、(n, m)的连通块,兔子一定不能从(1, 1)到(n, m)。
如果(1, 1)、(n, m)在同一连通块中,兔子一定可以从(1, 1)到(n, m)。
所以我们只要求出该图的最小割。
然而一共有 \(1000\times 1000\) 个点,显然直接上最大流会TLE(然而黄学长用一种神奇的方法过了)
所以我们考虑该图的特殊性。

注意到这是一个平面图,边之间互不相交。
我们把(1, 1)、(n, m)之间连一条边,然后把原图的每一个面当做一个点,相邻的面之间连边,除去连上(1, 1)和(n, m)新增的一个面和面积无限大的面之间的连边外,新图的最短路即为原图的最小割。

似乎只要是平面图就可以这样做。
代码如下: