問題文

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

各マス $(i,j)$ $(1≤i≤H,1≤j≤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≤H,W≤100$

• $0≤U,D,R,L≤100$

• $0≤K≤10^{13}$

• $0≤P≤10^{9}$

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

• $1≤x_s,x_t≤H$

• $1≤y_s,y_t≤W$

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

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

入力

$H\ W$

$U\ D\ R\ L\ K\ P$

$x_s\ y_s\ x_t\ y_t$

$C_{1,1}...C_{1,W}$

$\vdots$

$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≤i≤H)$

出力

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

サンプル