#3291. 「CEOI2014」城墙

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: PinkRabbit

题目描述

译自 CEOI 2014 Day2 T3「The Wall」,原网站因为神秘原因没法访问了,这里用的 Web Archive 链接。

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

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

必须保证从外部(也就是整个网格的外部)在不越过城墙的条件下,是到达不了任何一个村庄的。

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

地势测量表明,在每一段网格线上建造一段城墙都需要一定的花费。建造城墙的总花费就是建造每一段城墙的花费之和。如果在某一段网格线上建造了 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

样例输出 1

38

样例解释 1

pic1.png

样例输入 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

样例输出 2

22

样例解释 2

pic2.png

数据范围与提示

对于所有数据,保证 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 无特殊限制