問題文

縦 $H$ 行、横 $W$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。

各マス $(i,j)$ $(1\le i\le H,1\le j\le W)$ についての情報が $C_{i,j}$ で与えられます。

$C_{i,j}$ が.ならばマス $(i,j)$ は空マスであり、 $C_{i,j}$ が #ならばマス $(i,j)$ は固い壁マスであり、$C_{i,j}$ が @ならばマス $(i,j)$ は脆い壁マスです。

ロボットのT君は上下左右に隣り合うマスへの移動を繰り返し、マス $(x_s,y_s)$ から出発しマス $(x_t,y_t)$ に辿り着こうとしています。

T君は出発前に、ある非負整数 $x$ を選んでコスト $P\times x$ で脆い壁を $x$ 個破壊し、空マスにすることができます。

出発後T君がマス　$(i,j)$ にいるとき、以下の移動ができます。

• マス $(i-1,j)$ が空マスであるならば、マス $(i-1,j)$ にコスト $U$ で移動できる。

• マス $(i+1,j)$ が空マスであるならば、マス $(i+1,j)$ にコスト $D$ で移動できる。

• マス $(i,j+1)$ が空マスであるならば、マス $(i,j+1)$ にコスト $R$ で移動できる。

• マス $(i,j-1)$ が空マスであるならば、マス $(i,j-1)$ にコスト $L$ で移動できる。

T君がマス $(x_t,y_t)$ にコスト $K$ 以下で辿り着くことは可能でしょうか？

可能ならばYes、不可能ならばNoと出力してください。

制約

• $2\le H,W\le 100$

• $0\le U,D,R,L\le 100$

• $0\le K\le {10}^{13}$

• $0\le P\le {10}^9$

• $C_{i,j}$ は.または#または@である。

• $1\le x_s,x_t\le H$

• $1\le y_s,y_t\le W$

• $(x_s,y_s)\ne (x_t,y_t)$

• $(x_s,y_s)$,$(x_t,y_t)$ は空マスである。

入力

$HW$
$UDRLKP$
$x_s{y}_s{x}_t{y}_t$
$C_{1,1}...C_{1,W}$
$⋮$
$C_{H,1}...C_{H,W}$

• $1$ 行目には $H,W$ が空白区切りで与えれる。

• $2$ 行目には $U,D,R,L,K,P$ が空白区切りで与えれる。

• $3$ 行目には $x_s,y_s,x_t,y_t$ が空白区切りで与えられる。

• $4$ 行目から $H+3$ 行目には $C_{i,1}...C_{i,W}$ が与えれる。$(1\le i\le H)$

出力

答えを $1$ 行に出力してください。 最後に改行してください。

サンプル

3 3
1 1 1 1 8 16
1 1 3 1 
..@
##@
..@

No

2 2
0 0 0 0 1 1
1 1 2 2
.@
#.

Yes

2 2
100 100 100 100 100 104060401
1 1 2 2
.#
#.

No