Migrated from Lutece 2731 哈密顿回路

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

哈密顿有个 $n \times m$ 的网格，网格被一些水平的和竖直的带权边分成了 $n \times m$ 个小格子。

这时候，调皮的欧拉给网格上的一些格子染上了颜色，于是这些被染色的格子被称为特殊格。因此哈密顿想拿这个网格图来考验一下你。

现在你需要找到一条从左上格点出发的回路（即沿着格子的边走，走的路线是个环），这条回路满足所有特殊的格子都被走出的回路圈起来，即若要从网格图外部走到任意一个特殊的格子都一定会跟该回路相交。这样的路径被哈密顿称为“哈密顿回路”。

现在他想知道所以这样的回路中，边权和最短的一条。

注意：边可以重复走，但多次经过时代价也要被计算多次

Input

第一行两个正整数 $n, m$，分别表示网格的行数和列数。 接下来 $n$ 行，每行 $m$ 个数，每个数为 $0$ 或 $1$，若为 $0$ 则表示该格为普通格，若为 $1$ 则表示该格为特殊格，保证第 $1$ 行的第 $1$ 个数一定为 $1$ 。 接下来 $n$ 行，每行 $m+1$ 个非负整数，依次表示每一段竖直的网格线上的边权。 接下来 $n+1$ 行，每行 $m$ 个非负整数，依次表示每一段水平的网格线上的边权。

Output

输出一个数表示最小的“哈密顿回路”边权和

Samples

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

Constraints

$1 \leq n,m \leq 400$

边权：$1 \leq w_i \leq 10^9$

Resources

2022 UESTC ICPC Training for Graph