题目描述

译自 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$ 个非负整数，依次表示每一段水平的网格线上的建造花费。

输出格式

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

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

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$。