题目描述

小 Z 一觉醒来，发现自己在了一个迷宫之中，苦心探索了若干次，却仍然回到了起点。小 Z 绝望无比，此时，他决定听天由命。

具体来说，这个迷宫有 $n$ 行 $m$ 列，小 Z 现在位于 $(1,1)$，只要走到 $(n,m)$ 就可以马上离开迷宫。某些格子间有墙而无法通过，迷宫的周围也有一圈墙。而对于可以通过的地方，小 Z 决定按下述规则移动：在每个格子中，随机选择上下左右四个方向移动，概率由小 Z 按照自己的方向感确定，当然这个概率会满足下述要求：

1. 有墙的方向概率为 $0$。
2. 除了 $(n,m)$，每个格子往四个方向的概率加起来等于 $1$。
3. 一旦到了 $(n,m)$ 就马上离开迷宫，故从 $(n,m)$ 往任意方向的概率均为 $0$。

Your Task：

求出小 Z 离开迷宫的期望步数。

输入格式

第一行 $n,m$ 表示迷宫大小。

接下来 $4$ 个 $n \times m$ 的矩阵，第 $k$ 个矩阵的第 $i$ 行第 $j$ 列的数表示了在格子 $(i,j)$ 时往 $k$ 方向移动的概率，$k=1$ 为向下 $(i+1,j)$，$k=2$ 为向右 $(i,j+1)$，$k=3$ 为向上 $(i-1,j)$，$k=4$ 为向左 $(i,j-1)$ 。

由 $(n,m)$ 往任意方向走的概率均为 $0$。

输出格式

输出一个数表示答案，保留三位小数。

2 2
0.1 0.1
0 0
0.9 0
0.1 0
0 0
0.9 0
0 0.9
0 0

20.000

1 5
0.0 0.0 0.0 0.0 0.0
1.0 0.1 0.7 0.5 0.0
0.0 0.0 0.0 0.0 0.0
0.0 0.9 0.3 0.5 0.0

41.143

数据规模与约定

对于 $100\%$ 的数据：$1 \leq n,m \leq 50$，迷宫合法，一定可以走到终点，答案不超过 $10^7$。