Description

给出一个N×M的网格图，有一些方格里面存在城市，其中首都位于网格图的左上角。你可以沿着网格的边界走，要求你走的路线是一个环并且所有的城市都要被你走出来的环圈起来，即想从方格图的外面走到任意一个城市一定要和你走过的路线相交。你沿着方格的边界走是需要费用的，不同的边界费用可能不同。问你走出满足要求的环的最小代价。

1≤N，M≤400，走过边界的代价为正整数且不超过10。

Input

第一行有两个正整数 N，M，表示网格图的行数和列数。

接着一个 N×M 的 01 矩阵，如果该位置上是1则表示对应的方块里有一个城市。

之后一个 N×M+1 的矩阵，代表通过竖直的每个边界所需的花费。

最终一个N+1×M的矩阵，代表通过水平的每个边界所需的花费。

Output

输出一个数，表示最小的代价

Sample Input

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

Sample Output

38

Data Constraint

对于前10%的数据，N，M≤9。

对于前30%的数据，城市的数量不超过10。

对于前60%的数据，N，M<40。

Hint

样例解释：