Migrated from Lutece 3190 魔法守护

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$ 的地图区域右下角，现在有一股群恐怖的敌人正从这块区域的左上角向你袭来。由于你翘了过多的早八魔法课，现在的你并不能依靠魔法来解决掉敌人，但你可以通过魔法将部分道路封锁来达到阻止敌人前进的目的。

这块区域的网格有 $4$ 种状态：

$0$：这块区域没有任何什么特别的。 $1$：这块区域受到敌人魔法影响，方格周围的四条路径你不能施加魔法。 $2$：这块区域有一条左上角到右下角的路径。 $3$：这块区域有一条右上角到左下角的路径。

每一条路径上有对应的权值，代表你使用魔法封锁这条路径需要的消耗。

现在你不得不开始思考如何才能消耗最小的魔力来封锁敌人的前进路线。

Input

第一行两个整数 $n,m$，意义如题上所说。

接下来 $n$ 行，每行 $m$ 个整数，代表对应方格的状态。

接下来 $n+1$ 行，每行 $m$ 个整数，代表的是封锁这条横向路径需要的消耗。

接下来 $n$ 行，每行 $m+1$ 个整数，代表的是封锁这条竖向路径需要的消耗。

接下来 $n$ 行，每行 $m$ 个整数，如果该方格中有一条斜向边，代表封锁这条边需要的消耗。

Output

输出一个整数，代表能够阻止敌人前进的最小消耗。如果没有办法阻止敌人接近你，输出 -1。

Samples

2 2
0 1
2 3
1 2
3 4
5 6
7 8 9
10 11 12
0 0 
13 14

8

1 3
1 1 1
1 1 4
5 1 4
1 9 1 9
0 0 0

-1

Constraints

$1\le n\times m\le 5\times10^5$。

$1\le w\le10^6$，$w$ 代表每条边权值。

Note

样例一如图所示：

Resources

2024 UESTC ICPC Training for Graph