#line 2 "lib/prelude.hpp" #ifndef LOCAL #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #endif #include using namespace std; using ll = long long; #define rep2(i, m, n) for (auto i = (m); i < (n); i++) #define rep(i, n) rep2(i, 0, n) #define repr2(i, m, n) for (auto i = (n); i-- > (m);) #define repr(i, n) repr2(i, 0, n) #define all(x) begin(x), end(x) template auto ndvec(size_t n, T&& x) { return vector(n, forward(x)); } template auto ndvec(size_t n, Ts&&... xs) { return vector(n, forward(xs)...); } #line 3 "lib/graph.hpp" struct unit_edge { int to; operator int() const { return to; } int w() const { return 1; } }; template struct weighted_edge { int to; Weight weight; operator int() const { return to; } Weight w() const { return weight; } }; template struct basic_graph { using weight_type = void; const Inner& inner; basic_graph(const Inner& g) : inner(g) {} template void adj(int v, F f) const { for (auto u : inner[v]) f(unit_edge{u}); } }; template struct basic_weighted_graph { using weight_type = Weight; const Inner& inner; basic_weighted_graph(const Inner& g) : inner(g) {} template void adj(int v, F f) const { for (auto [u, w] : inner[v]) f(weighted_edge{u, w}); } }; template struct graph_trait { using weight_type = typename Inner::weight_type; const Inner& g; graph_trait(const Inner& g) : g(g) {} int size() const { return g.size(); } template void adj(int v, F f) const { g.adj(v, f); } }; template constexpr bool is_weighted_v = !is_same_v::weight_type, void>; template using weight_t = conditional_t, typename graph_trait::weight_type, int>; template using edge_t = conditional_t, weighted_edge>, unit_edge>; template struct graph_trait[N]> : basic_graph[N]> { using basic_graph[N]>::basic_graph; int size() const { return N; } }; template <> struct graph_trait>> : basic_graph>> { using basic_graph>>::basic_graph; int size() const { return this->inner.size(); } }; template struct graph_trait>[N]> : basic_weighted_graph>[N], Weight> { using basic_weighted_graph>[N], Weight>::basic_weighted_graph; int size() const { return N; } }; template struct graph_trait>>> : basic_weighted_graph>>, Weight> { using basic_weighted_graph>>, Weight>::basic_weighted_graph; int size() const { return this->inner.size(); } }; #line 3 "lib/func/constant.hpp" template struct constant { template constexpr T operator()(Ts&&...) const { return val; } }; #line 4 "lib/graph/grid.hpp" enum direction { Left, Right, Up, Down }; template , char Wall = '#'> class grid_graph { public: template grid_graph(It grid, It grid_last, Weight c = Weight()) : h(grid_last - grid + 2), w(grid[0].size() + 2), c(c), data(h * w, Wall) { rep(i, h - 2) copy(all(grid[i]), data.begin() + (i + 1) * w + 1); } int map(int r, int c) const { return (r + 1) * w + c + 1; } char operator[](int i) const { return data[i]; } char operator[](int i[2]) const { return data[map(i[0], i[1])]; } using weight_type = invoke_result_t; int size() const { return h * w; } template void adj(int v, F f) const { if (data[v] == Wall) return; int d[] = {-1, 1, -w, w}; rep(i, 4) if (data[v + d[i]] != Wall) f(edge_t{v + d[i], c(data[v + d[i]], i)}); } private: int h, w; Weight c; vector data; }; #line 3 "lib/graph/dijkstra.hpp" template vector> dijkstra(const G& graph, Iter s_it, Iter s_last) { graph_trait g(graph); vector> dist(g.size(), numeric_limits>::max()); priority_queue, int>, vector, int>>, greater<>> hp; while (s_it != s_last) hp.emplace(weight_t(0), *s_it), dist[*s_it++] = weight_t(0); while (!hp.empty()) { auto [w, v] = hp.top(); hp.pop(); if (w != dist[v]) continue; g.adj(v, [&](auto&& e) { if (dist[e.to] > dist[v] + e.w()) dist[e.to] = dist[v] + e.w(), hp.emplace(dist[e.to], e.to); }); } return dist; } template vector> dijkstra(const G& graph, int s) { return dijkstra(graph, &s, &s + 1); } #line 3 "lib/io.hpp" template class stdin_reader { public: stdin_reader() { buf[fread_unlocked(buf, 1, sizeof(buf), stdin)] = 0; } template enable_if_t> read(T& x) { skip(); [[maybe_unused]] bool neg = false; if constexpr (is_signed_v) neg = *p == '-' ? (p++, true) : false; x = 0; while (*p > ' ') x = x * 10 + (*p++ & 0x0F); if constexpr (is_signed_v) x = neg ? -x : x; } template void_t read(T& x) { x = T((unsigned)(*this)); } void read(char* q) { skip(); char* p0 = p; while (*p > ' ') p++; copy(p0, p, q); } template void read(char (&s)[N]) { read(s); } void read(string& s) { skip(); char* p0 = p; while (*p > ' ') p++; s.assign(p0, p); } template void read(pair& x) { read(x.first), read(x.second); } template void read(tuple& x) { read_tuple(x, make_index_sequence{}); } template void read(T (&a)[N]) { for (auto& e : a) read(e); } template operator T() { T x; return read(x), x; } template void operator()(Ts&... xs) { (read(xs), ...); } int operator--() { return (int)*this - 1; } template void vec(vector& v, int n) { v.resize(n); for (auto& e : v) read(e); } template vector vec(int n) { vector v(n); return vec(v, n), v; } private: char buf[BUF_SIZE], *p = buf; void skip() { while (*p <= ' ') p++; } template void read_tuple(T& x, index_sequence) { (*this)(get(x)...); } }; template class stdout_writer { public: ~stdout_writer() { flush(); } void flush() { fwrite_unlocked(buf, 1, p - buf, stdout), p = buf; } void write_char(char c) { *p++ = c; } void write(char c) { write_char(c); } template enable_if_t> write(T x) { if (!x) return write_char('0'); if constexpr (is_signed_v) if (x < 0) write_char('-'), x = -x; static char tmp[16]; char* q = end(tmp); while (x >= 10000) memcpy(q -= 4, four_digits.data + x % 10000 * 4, 4), x /= 10000; if (x < 10) write_char('0' + x); else if (x < 100) write_char('0' + (uint8_t)x / 10), write_char('0' + (uint8_t)x % 10); else if (x < 1000) memcpy(p, four_digits.data + x * 4 + 1, 3), p += 3; else memcpy(p, four_digits.data + x * 4, 4), p += 4; memcpy(p, q, end(tmp) - q), p += end(tmp) - q; } template void_t write(T x) { write(x.val()); } void write(const char* s) { p = stpcpy(p, s); } void write(const string& s) { memcpy(p, s.c_str(), s.size()), p += s.size(); } template void write(const pair& x) { write(x.first), write_char(' '), write(x.second); } template void write(const tuple& x) { write_tuple(x, make_index_sequence{}); } template void write(const Ts&... xs) { ((write(xs), write_char(' ')), ...), --p; } template void writeln(const Ts&... xs) { write(xs...), write_char('\n'); } template void operator()(const Ts&... xs) { writeln(xs...); } template void iter(It first, It last) { while (first != last) write(*first++), write_char(' '); p[-1] = '\n'; } #define INSTANT(s) \ void s() { writeln("s"); } INSTANT(No) INSTANT(NO) INSTANT(Aoki) INSTANT(possible) INSTANT(Possible) INSTANT(POSSIBLE) INSTANT(impossible) INSTANT(Impossible) INSTANT(IMPOSSIBLE) #undef INSTANT void Yes(bool b = true) { writeln(b ? "Yes" : "No"); } void YES(bool b = true) { writeln(b ? "YES" : "NO"); } void Takahashi(bool b = true) { writeln(b ? "Takahashi" : "Aoki"); } private: char buf[BUF_SIZE], *p = buf; template void write_tuple(const T& x, index_sequence) { ((write(get(x)), write_char(' ')), ...), --p; } struct four_digits { char data[40000]; constexpr four_digits() : data() { for (int i = 0; i < 10000; i++) for (int n = i, j = 4; j--;) data[i * 4 + j] = n % 10 + '0', n /= 10; } } static constexpr four_digits{}; }; static stdin_reader<> in; static stdout_writer<> out; #line 4 "main.cpp" int main() { int h = in, w = in, u = in, d = in, r = in, l = in; ll k = in, p = in; int xs = --in, ys = --in, xt = --in, yt = --in; auto grid = in.vec(h); auto weight = [=](char c, int dir) { return (c == '@' ? p : 0) + ((int[]){l, r, u, d})[dir]; }; grid_graph graph(all(grid), weight); ll ans = dijkstra(graph, graph.map(xs, ys))[graph.map(xt, yt)]; out.Yes(ans <= k); (void)w; }