题目背景

由于震惊海内外的“愤怒门投毒事件”的发生，部落为了对抗皇家药剂师协会的叛乱，所有的外交工作完成后，部落大酋长萨尔带领着小A穿过传送门到达幽暗城平叛。

题目描述

幽暗城的地图是一个 $n×m$ 的 $01$ 串。$a_{i,j}=1$ 时表示 $(i,j)$ 的位置是障碍，无法通过；$a_{i,j}=0$ 时表示 $(i,j)$ 的位置可以进入。

小A与萨尔的初始位置是 $(x_1,y_1)$，而恐惧魔王的初始位置是 $(x_2,y_2)$。小A的目标就是到达恐惧魔王的位置。

萨尔会按照一个特定的路线行走，该路线是一个数字串，由 $0-4$ 组成。

第 $i$ 秒，若数字串第（$i \, \bmod$ 数字串的长度）位等于 $0$，则表示这一秒萨尔将会原地不动；

等于 $1$，则表示这一秒萨尔会向上走一格；

等于 $2$，则表示这一秒萨尔会向下走一格；

等于 $3$，则表示这一秒萨尔会向左走一格；

等于 $4$，则表示这一秒萨尔会向右走一格。

若萨尔将要移动的位置是墙或者超出迷宫的范围，则萨尔会原地不动。恐惧魔王也是这样。（换句话说，你可以认为如果将数字串是重复无限次，第 $i$ 秒就是字符串第 $i$ 位）

小A每秒可以选择从上下左右四个方向中选择一个方向，朝那个方向走一格，前提是那个位置不是墙并且没有超出迷宫的范围；或者原地不动。不过，由于幽暗城的诡异环境，小A只能持续脱离萨尔的光环 $s$ 秒，若超过 $s$ 秒小A则会死亡。光环的有效半径为 $d$ ，表示当小A与萨尔之间的距离 $\sqrt{(x-xx)^2+(y-yy)^2}$ 小于等于 $d$ 时小A才能受到萨尔光环的效果。若小A脱离萨尔的光环又重新进入光环有效区域，则再次离开光环时持续时间归零重记。

小A想知道最少需要几秒他才能到达恐惧魔王所在的位置。

输入格式

第一行四个数 $n$，$m$，$s$，$d$。

接下来的 $n$ 行，每行 $m$ 个数（$0$ 或 $1$），之间没有空格，表示幽暗城的地图。

接下来的一行四个整数，$x_1$，$y_1$，$x_2$，$y_2$（$1 \le x_1$，$x_2 \le n$，$1 \le y_1$，$y_2 \le m$）。

接下来的一行是一个数字串，表示萨尔的移动方式。

接下来的一行是一个数字串，表示恐惧魔王的移动方式。

输出格式

一行一个整数，表示需要最少的时间。

说明/提示

【题目来源】

kiro原创

【数据规模】

对于 $100\%$ 的数据，$1 \le n$，$m \le 50$，$0 \le s \le 1000$，$0 \le d \le 100$，$1 \le$ 数字串长度 $\le 100$，$0 \le$ 答案 $\le 100$。

题目背景

由于震惊海内外的“愤怒门投毒事件”的发生，部落为了对抗皇家药剂师协会的叛乱，所有的外交工作完成后，部落大酋长萨尔带领着小A穿过传送门到达幽暗城平叛。

题目描述

幽暗城的地图是一个 $n×m$ 的 $01$ 串。$a_{i,j}=1$ 时表示 $(i,j)$ 的位置是障碍，无法通过；$a_{i,j}=1$ 时表示 $(i,j)$ 的位置可以进入。

小$A$与萨尔的初始位置是 $(x_1,y_1)$，而恐惧魔王的初始位置是 $(x_2,y_2)$。小A的目标就是到达恐惧魔王的位置。

萨尔会按照一个特定的路线行走，该路线是一个数字串，由 $0-4$ 组成。

第 $i$ 秒，若数字串第（$i \, \bmod $ 数字串的长度）位等于 $0$，则表示这一秒萨尔将会原地不动； 

等于 $1$，则表示这一秒萨尔会向上走一格； 

等于 $2$，则表示这一秒萨尔会向下走一格； 

等于 $3$，则表示这一秒萨尔会向左走一格； 

等于 $4$，则表示这一秒萨尔会向右走一格。

若萨尔将要移动的位置是墙或者超出迷宫的范围，则萨尔会原地不动。恐惧魔王也是这样。（换句话说，你可以认为如果将数字串是重复无限次，第 $i$ 秒就是字符串第  $i$ 位）

小A每秒可以选择从上下左右四个方向中选择一个方向，朝那个方向走一格，前提是那个位置不是墙并且没有超出迷宫的范围；或者原地不动。不过，由于幽暗城的诡异环境，小A只能持续脱离萨尔的光环 $s$ 秒，若超过 $s$ 秒小A则会死亡。光环的有效半径为 $d$ ，表示当小A与萨尔之间的距离 $\sqrt{((x-xx)^2+(y-yy)^2)}$ 小于等于 $d$ 时小A才能受到萨尔光环的效果。若小A脱离萨尔的光环又重新进入光环有效区域，则再次离开光环时持续时间归零重记。

小A想知道最少需要几秒他才能到达恐惧魔王所在的位置。

输入格式

第一行四个数 $n$，$m$，$s$，$d$。

接下来的 $n$ 行，每行 $m$ 个数（$0$ 或 $1$），之间没有空格，表示幽暗城的地图。

接下来的一行四个整数，$x_1$，$y_1$，$x_2$，$y_2$（$1 \le x_1$，$x_2 \le n$，$1 \le y_1$，$y_2 \le m$）。

接下来的一行是一个数字串，表示萨尔的移动方式。

接下来的一行是一个数字串，表示恐惧魔王的移动方式。

输出格式

一行一个整数，表示需要最少的时间。

说明/提示

【题目来源】

kiro原创

【数据规模】

对于 $100\%$ 的数据，$1 \le n$，$m \le 50$，$0 \le s \le 1000$，$0 \le d \le 100$，$1 \le   $ 数字串长度 $   \le 100$，$0 \le $ 答案 $ \le 100$。