class dijkstra:
def __init__(self,V):
self.INF=float("inf")
self.G=[[] for _ in [0]*V]
self.V=V
return
def add1(self,s,t,v):
self.G[s].append([t,v])
return
def add2(self,s,t,v):
self.G[s].append([t,v])
self.G[t].append([s,v])
return
def run(self,s):
from heapq import heapify,heappop,heappush
ret=[self.INF]*self.V
que=[]
heapify(que)
ret[s]=0
heappush(que,(0,s))
while que:
p=heappop(que)
v=p[1]
if ret[v]
ret[v]+e[1]:
ret[e[0]]=ret[v]+e[1]
heappush(que,(ret[e[0]],e[0]))
return ret
def pop_back(self,x):
self.G[x].pop()
return
def size(self,x):
return len(self.G[x])
class INPUT:
def __init__(self):
self._l=open(0).read().split()
self._length=len(self._l)
self._index=0
return
def stream(self,k=1,f=int,f2=False):
assert(-1 return left all
listを変数で受け取るとき、必ずlistをTrueにすること。
"""
def main():
ans=float("inf")
H,W,U,D,R,L,K=pin(7)
co=(U+1)*(D+1)*(R+1)*(L+1)
C=[]
B=[]
for i in range(H):
C.append(list(pin(1,str)))
for j in range(W):
if C[i][j]=="$":
B.append((i,j))
C[-1].append("#")
C.append(["#"]*W)
xs,ys,xt,yt=pin(4)
xs-=1
ys-=1
xt-=1
yt-=1
V=H*W
ijk=dijkstra(V)
for i in range(H):
for j in range(W):
if C[i][j]=="#":
continue
if C[i+1][j]==".":
ijk.add1(W*i+j,W*(i+1)+j,D)
ijk.add1(W*(i+1)+j,W*i+j,U)
if C[i][j+1]==".":
ijk.add1(W*i+j,W*i+j+1,R)
ijk.add1(W*i+j+1,W*i+j,L)
defa=[]
for i in range(V):
defa.append(ijk.size(i))
cnt=len(B)
m=pow(2,cnt)
for i in range(m):
u=[]
for j in range(cnt):
if (i>>j)&1:
x=B[j][0]
y=B[j][1]
u.append((x,y))
C[x][y]="."
for j in range(cnt):
if (i>>j)&1:
x=B[j][0]
y=B[j][1]
if C[x+1][y]==".":
ijk.add1(W*x+y,W*(x+1)+y,D)
ijk.add1(W*(x+1)+y,W*x+y,U)
if C[x][y+1]==".":
ijk.add1(W*x+y,W*x+y+1,R)
ijk.add1(W*x+y+1,W*x+y,L)
if x>0 and C[x-1][y]==".":
ijk.add1(W*x+y,W*(x-1)+y,U)
ijk.add1(W*(x-1)+y,W*x+y,D)
if y>0 and C[x][y-1]==".":
ijk.add1(W*x+y,W*x+y-1,L)
ijk.add1(W*x+y-1,W*x+y,R)
d=ijk.run(W*xs+ys)
ans=min(ans,d[W*xt+yt]+len(u)*co)
for i in range(V):
while ijk.size(i)>defa[i]:
ijk.pop_back(i)
for j in u:
C[j[0]][j[1]]="$"
if ans<=K:
print("Yes")
else:
print("No")
return
main()