Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i,j)$.

Information about each cell $(i,j)$ $(1≤i≤H,1≤j≤W)$ is given by $C_{i,j}$.

If $C_{i,j}$ is ., the cell $(i,j)$ is an empty cell; if $C_{i,j}$ is #, the cell $(i,j)$ is a hard wall cell; and if $C_{i,j}$ is @, the cell $(i,j)$ is a fragile wall cell.

The robot T-kun repeatedly moves to a vertically or horizontally adjacent cell, trying to start from the cell $(x_s,y_s)$ and reach the cell $(x_t,y_t)$.

Before departure, T-kun can choose a non-negative integer $x$ and, at a cost of $P\times x$, destroy $x$ fragile walls, turning them into empty cells.

After departure, when T-kun is at the cell $(i,j)$, the following moves are available.

• If the cell $(i-1,j)$ is an empty cell, T-kun can move to the cell $(i-1,j)$ at a cost of $U$.

• If the cell $(i+1,j)$ is an empty cell, T-kun can move to the cell $(i+1,j)$ at a cost of $D$.

• If the cell $(i,j+1)$ is an empty cell, T-kun can move to the cell $(i,j+1)$ at a cost of $R$.

• If the cell $(i,j-1)$ is an empty cell, T-kun can move to the cell $(i,j-1)$ at a cost of $L$.

Is it possible for T-kun to reach the cell $(x_t,y_t)$ with a cost of at most $K$?

If it is possible, print Yes; otherwise, print No.

Constraints

• $2≤H,W≤100$

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

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

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

• $C_{i,j}$ is ., #, or @.

• $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)$ are empty cells.

Input

$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}$

• The $1$st line contains $H,W$ separated by spaces.

• The $2$nd line contains $U,D,R,L,K,P$ separated by spaces.

• The $3$rd line contains $x_s,y_s,x_t,y_t$ separated by spaces.

• Lines $4$ through $H+3$ contain $C_{i,1}...C_{i,W}$. $(1≤i≤H)$

Output

Print the answer on $1$ line. Print a newline at the end.

Sample

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