Rectos 岛经常受到洪水和海盗的威胁。因此，Rectos 国王希望用一堵巨大的围墙来保护岛上的所有村庄。

Rectos 呈矩形。因此，围墙的设计师将该岛建模为一个网格。每个村庄都位于其中一个方格内；首都村庄位于最西北角，即左上角的方格内。

围墙的建造方式必须使得从外部（即网格外部的区域）在不跨越围墙的情况下无法到达任何村庄。

设计师计划仅沿着网格线建造围墙，具体方式如下：他将第一段墙放在从左上角开始的两条网格线段之一上。然后，下一段墙总是与前一段相连，即建造在相邻的网格线段上（该线段起点为前一段的终点）。设计师继续这种方式，直到再次回到左上角。这个过程可能会导致在同一条网格线段上放置多于一段的墙。也就是说，围墙是沿着一条连续的闭合网格线段路径建造的。

由于地形原因，对于每条网格线段，在其上建造一段围墙都有一定的成本。建造围墙的总成本由所有围墙段的成本之和给出。如果在同一条网格线段上建造了 $t$ 段围墙，则该网格线段的成本将被计算 $t$ 次。

国王希望花尽可能少的钱来建造围墙。帮助国王编写一个程序，在给定岛上村庄的位置以及所有网格线段的建造成本的情况下，计算建造围墙的最小成本。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示网格的行数和列数。

接下来的 $N$ 行描述网格的行。这些行中的每一行都包含 $M$ 个整数，为 $0$ 或 $1$：$0$ 表示空方格，而 $1$ 表示该方格中存在村庄。这些行中第一行的第一个整数为 $1$。

随后有 $N$ 行，每行包含 $M + 1$ 个非负整数：这些数字指定了沿着相应垂直网格线段建造围墙段的成本。

最后有 $N + 1$ 行，每行包含 $M$ 个非负整数：这些数字指定了沿着相应水平网格线段建造围墙段的成本。

输出格式

输出的唯一一行应包含一个整数：建造围墙的最小成本。

数据范围

满足 $1 \le N, M \le 400$，且对于所有成本值 $v$，有 $1 \le v \le 10^9$。然而，你可能需要使用 long long 来存储结果！

• 子任务 1 (30 分)：村庄数量不超过 $10$，且 $N, M \le 40$。
• 子任务 2 (30 分)：$N, M \le 40$。
• 子任务 3 (40 分)：无附加限制。

样例

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

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

说明

下图展示了上述两种情况以及对应的最优围墙方案。在这两种情况下，围墙均以粗线表示，含有村庄的方格被着色。