「CEOI2014」城墙

译自 CEOI 2014 Day2 T3「The Wall」

题目描述

Rectos 岛经常遭受洪水和海盗的侵扰，所以 Rectos 的国王想要建造一堵城墙以保护岛上所有的村庄。

Rectos 是一个矩形岛屿，城墙的设计师将岛屿看作一个 $n \times m$ 的正方形网格。每个村庄都位于其中的某个方格中，并且首都村庄位于整座岛的西北角，也就是最左上角的方格中。

必须保证从外部（也就是整个网格的外部）在不越过城墙的条件下，无法到达任何一个村庄。

设计师计划城墙将只沿着网格线建造，具体建造方法如下：他将第一段城墙置于最左上角延伸出的两条网格线之一上，并且下一段城墙总是和上一段城墙首尾相连，不断重复这一过程直到又一次回到最左上角为止。这一过程可能会导致一段网格线上放置了多段城墙，总而言之，城墙是沿着网格线上的一条连续闭曲线建造的。

地势测量表明，在每一段网格线上建造一段城墙都需要一定的花费。建造城墙的总花费就是建造每一段城墙的花费之和。如果在某一段网格线上建造了 $t$ 段城墙，则花费也要重复计算 $t$ 次。

国王想要花费尽量少的钱建好城墙。请你帮助国王，编写一个程序，给出村庄的位置以及每一段网格线上的建造花费，计算建造城墙所需的最小花费。

输入格式

• 第一行两个正整数 $n, m$，分别表示网格的行数和列数。
• 接下来 $n$ 行，每行 $m$ 个数，每个数为 $0$ 或 $1$：
  • 若为 $0$ 则表示该格没有村庄
  • 若为 $1$ 则表示该格有村庄
  • 保证第 $1$ 行的第 $1$ 个数一定为 $1$
• 接下来 $n$ 行，每行 $m + 1$ 个非负整数，依次表示每一段竖直的网格线上的建造花费
• 接下来 $n + 1$ 行，每行 $m$ 个非负整数，依次表示每一段水平的网格线上的建造花费

输出格式

输出一行一个数表示建造城墙的最小花费。

样例 1

输入

3 3
1 0 0
1 0 0
0 0 1
1 4 9 4
1 6 6 6
1 2 2 9
1 1 1
4 4 4
2 4 2
6 6 6

输出

38

样例 2

输入

3 3
1 0 1
0 0 0
0 1 0
2 1 1 3
5 6 1 1
2 1 1 3
2 1 1
3 4 1
4 1 1
5 1 2

输出

22

数据范围与提示

对于所有数据，保证：

• $1 \le n, m \le 400$
• 对于所有的建造花费 $v$，有 $1 \le v \le 10^9$

子任务

子任务编号	分值	特殊限制
1	30	$n, m \le 40$ 且村庄的数量不超过 $10$
2		$n, m \le 40$
3	40	无特殊限制

---

补充说明

• 城墙必须形成一个闭合回路，从左上角开始并回到左上角
• 城墙必须包围所有有村庄的格子
• 同一段网格线可能被多次使用，每次使用都要计算花费
• 目标是找到总花费最小的城墙建造方案