Migrated from Lutece 2973 Lily Lycoris Recoil

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$ 的网格道路组成的区域，其中每个网格会有四种情况：

1. 该网格有一个敌人的哨塔，则网格周围的四条路都不能设置攻击型无人机。
2. 该网格有一条左上角到右下角的路。
3. 该网格有一条右上角到左下角的路。
4. 该网格是一个空网格，仅有周围四条路围着。

所有的路均为双向通行的。

此时，恐怖分子的军队会乘车从网格营地的左上角出发，前往右下角的大本营。由于每条路的情况不同，布置攻击型无人机的费用也会不一样，你需要帮助胡桃以最小的代价选择一些道路，布置好无人机，使得无论恐怖分子走那条路，都能有无人机截击消灭掉他们。为了以防万一，千束和泷奈也已经在大本营埋伏着等待漏网之鱼。

恐怖分子就快要出发了，时间迫在眉睫，你需要以最快的速度告诉千束和泷奈她们是否需要迎击敌人，如果不需要则请计算出无人机布置的最小代价。

Input

第一行两个数字 $n,m$ 表示恐怖分子营地大小。

接下来 $n$ 行 $m$ 列数字，表示每个网格区域的类型，如果是 $0$ 代表是个空网格，如果是 $1$ 代表有哨塔， 如果是 $2$ 则代表有左上角到右下角的路，如果是 $3$ 则代表有左下角到右上角的路。

接下来 $n+1$ 行，每行 $m$ 个数字，表示水平道路布置无人机的代价 $h_{ij}$。

接下来 $n$ 行，每行 $m+1$ 个数字，表示垂直道路布置无人机的代价 $v_{ij}$。

接下来 $n$ 行，每行 $m$ 个数字，如果大于 $0$, 则表示倾斜的道路布置无人机的代价 $x_{ij}$，否则该网格无倾斜道路。

Output

如果不需要千束和泷奈她们迎击敌人，则输出最小布置无人机代价，否则输出Lycoris!。

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

Lycoris!

Constraints

$$1\leq n\times m\leq 5\times 10^5\\ 1\leq x_{ij},v_{ij},h_{ij}\leq 10^6 $$

Note

两个样例地图如下：

Resources

2023 UESTC ICPC Training for Graph