#include /* #include #include namespace mp = boost::multiprecision; using bint = mp::cpp_int; */ #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for (int i = 0; i < int(n); ++i) #define repp(i,n,m) for (int i = m; i < int(n); ++i) #define repb(i,n) for (int i = int(n)-1; i >= 0; --i) #define fi first #define se second #define endl "\n" using namespace std; using namespace atcoder; //using namespace internal; using ll = long long; using ld = long double; using P = pair; using PL = pair; using Pxy = pair; const int INF = 1001001007; const long long mod1 = 1000000007LL; const long long mod2 = 998244353LL; const ll inf = 2e18; const ld pi = 3.14159265358979323; templatevoid priv(vector &v){if(v.size()==0){cout<void privv(vector> &v){rep(i,v.size()){rep(j,v[i].size()-1)cout<bool range(T a,T b,T x){return (a<=x&&xbool rrange(pair a,pair b,pair x){return (range(a.fi,b.fi,x.fi)&&range(a.se,b.se,x.se));} templatevoid rev(vector &v){reverse(v.begin(),v.end());} templatevoid sor(vector &v, int f=0){sort(v.begin(),v.end());if(f!=0) rev(v);} templatebool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;} templatebool chmax(T &a,const T &b){if(avoid eru(vector &v){sor(v);v.erase(unique(v.begin(),v.end()),v.end());} templateT cel(T a,T b){if (a%b==0)return a/b;return a/b +1;} template void pout(pair p){cout<void myswap(T &a,T &b){if(a>b)swap(a,b);} void yes(){cout << "Yes" << endl;} void no (){cout << "No" << endl;} void yn (bool t){if(t)yes();else no();} void Yes(){cout << "YES" << endl;} void No (){cout << "NO" << endl;} void YN (bool t){if(t)Yes();else No();} void dout() {cout << setprecision(20);} void deb(ll h = INF-1) {cout << (h == INF-1 ? "!?" : to_string(h)) << endl;} void revs(string &s) {reverse(s.begin(),s.end());} vector dx = {0,1,0,-1}; vector dy = {1,0,-1,0}; const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string alp = "abcdefghijklmnopqrstuvwxyz"; const string num = "0123456789"; ll gcds(ll a, ll b){ a = abs(a); b = abs(b); if (b == 0) return a; ll c = a % b; while (c != 0){ a = b; b = c; c = a % b; } return b; } ll tentou(vector ar){ int n = ar.size(); set st; rep(i,n) st.insert(ar[i]); map mp; int ind = 0; for (ll x : st){ mp[x] = ind; ind++; } fenwick_tree fw(ind); ll ans = 0; rep(i,n){ int a = mp[ar[i]]; ans += i - fw.sum(0,a+1); fw.add(a,1); } return ans; } struct vs{ vector> to; }; struct Graph{ using pli = pair; using pil = pair; int n, m; vector ar; // n : 頂点数 , m : 辺数 , c = 1 : コストを入力 , dual = 1 : 辺が双方向 Graph(int _n, int _m, int c = 1, int dual = 1) : n(_n), m(_m), ar(n) { for (int i = 0; i < m; i++){ int u, v; cin >> u >> v; long long d = 1; if (c == 1) cin >> d; ar[u-1].to.emplace_back(pil(v-1,d)); if (dual == 1) ar[v-1].to.emplace_back(pil(u-1,d)); } } Graph(vector _ar, int _n, int _m = 0) : ar(_ar), n(_n), m(_m){} vector dijkstra(int s){ priority_queue, greater> pque; vector dist(n,1e18); dist[s] = 0; pque.push(pli(0,s)); while (!pque.empty()){ pli p = pque.top(); pque.pop(); if (dist[p.second] < p.first) continue; for (pil x : ar[p.second].to){ if (dist[x.first] > p.first + x.second){ dist[x.first] = p.first + x.second; pque.push(pli(dist[x.first],x.first)); } } } return dist; } vector> washall_floyd(){ vector> dist(n,vector(n,2e18)); for (int i = 0; i < n; i++) dist[i][i] = 0; for (int i = 0; i < n; i++){ for (pil x : ar[i].to){ dist[i][x.first] = min(dist[i][x.first], x.second); } } for (int k = 0; k < n; k++){ for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } return dist; } }; /* alias g++='g++ -I/mnt/c/Users/Owner/Desktop/ac-library' */ int main(){ using pil = pair; int h, w; cin >> h >> w; vector cost(4); cin >> cost[3] >> cost[1] >> cost[0] >> cost[2]; rep(i,4) cost[i] *= 2; ll ka, p; cin >> ka >> p; ka *= 2; int a, b, c, d; cin >> a >> b >> c >> d; int s = w * (a-1) + b-1; int g = w * (c-1) + d-1; vector> maze(h,vector(w)); rep(i,h) rep(j,w) cin >> maze[i][j]; vector ar(h*w); rep(i,h) rep(j,w){ if (maze[i][j] == '#') continue; int f = i * w + j; ll pl = (maze[i][j] == '@' ? p : 0); rep(k,4){ if (rrange(P(0,0),P(h,w),P(i+dx[k],j+dy[k]))){ if (maze[i+dx[k]][j+dy[k]] == '#') continue; int t = (i+dx[k]) * w + j+dy[k]; ll y = pl; if (maze[i+dx[k]][j+dy[k]] == '@') y += p; ar[f].to.emplace_back(pil(t,cost[k] + y)); } } } Graph gr(ar,h*w); auto v = gr.dijkstra(s); yn(v[g] <= ka); //cout << v[g] << endl; //priv(v); //priv(cost); }