#1001. [BJOI2006] 狼抓兔子

[BJOI2006] 狼抓兔子

题目描述

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

左上角点为 (1,1)(1, 1),右下角点为 (n,m)(n, m)(上图中 n=3n = 3m=4m = 4)。有以下三种类型的道路:

  1. (x,y)(x+1,y)(x, y) \leftrightarrow (x + 1, y)
  2. (x,y)(x,y+1)(x, y) \leftrightarrow (x, y + 1)
  3. (x,y)(x+1,y+1)(x, y) \leftrightarrow (x + 1, y + 1)

道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的。左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角 (1,1)(1, 1) 的窝里,现在它们要跑到右下角 (n,m)(n, m) 的窝中去,狼王开始伏击这些兔子。当然为了保险起见,如果一条道路上最多通过的兔子数为 kk,狼王需要安排同样数量的 kk 只狼,才能完全封锁这条道路。

你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦。

输入格式

第一行两个整数 n,mn, m,表示网格的大小。

接下来分三部分:

  • 第一部分共 nn 行,每行 m1m-1 个数,表示横向道路的权值;
  • 第二部分共 n1n - 1 行,每行 mm 个数,表示纵向道路的权值;
  • 第三部分共 n1n - 1 行,每行 m1m - 1 个数,表示斜向道路的权值。

输出格式

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

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
14

数据范围

对于 100%100\% 的数据,3n,m1033 \leq n, m \leq 10^3,所有道路的权值均为不超过 10610^6 的正整数。