#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") // #pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl") using ll = long long; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } constexpr int dx[4] = {-1, 1, 0, 0}; constexpr int dy[4] = {0, 0, 1, -1}; constexpr ll inf = 1e+17; ll dp[105][105][305]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H, W, P, sx, sy, tx, ty; ll K; vector cost(4); cin >> H >> W; for(int i = 0; i < 4; ++i) cin >> cost[i]; cin >> K >> P >> sx >> sy >> tx >> ty; --sx, --sy, --tx, --ty; vector s(H); for(int i = 0; i < H; ++i) cin >> s[i]; for(int i = 0; i < H; ++i){ for(int j = 0; j < W; ++j){ for(int k = 0; k <= 205; ++k){ dp[i][j][k] = inf; } } } dp[sx][sy][0] = 0; using node = tuple; priority_queue, greater> que; que.emplace(0, sx, sy, 0); while(!que.empty()){ auto [d, x, y, cnt] = que.top(); que.pop(); if(d > dp[x][y][cnt]) continue; for(int i = 0; i < 4; ++i){ int nx = x + dx[i], ny = y + dy[i]; if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue; if(s[nx][ny] == '#') continue; if(s[nx][ny] == '.'){ if(chmin(dp[nx][ny][cnt], dp[x][y][cnt] + cost[i])){ que.emplace(dp[nx][ny][cnt], nx, ny, cnt); } } else{ if(cnt < 205 && chmin(dp[nx][ny][cnt + 1], dp[x][y][cnt] + cost[i] + P)){ que.emplace(dp[nx][ny][cnt + 1], nx, ny, cnt + 1); } } } } for(int i = 0; i <= 205; ++i){ if(dp[tx][ty][i] <= K) return puts("Yes") & 0; } cout << "No\n"; return 0; }