local mfl, mce = math.floor, math.ceil local mmi, mma = math.min, math.max local pow2 = {1} for i = 2, 28 do pow2[i] = pow2[i - 1] * 2 end local SegTree = {} SegTree.updateAll = function(self) for i = self.stagenum - 1, 1, -1 do local cnt = pow2[i] for j = 0, cnt - 1 do self.stage[cnt + j] = self.func(self.stage[(cnt + j) * 2], self.stage[(cnt + j) * 2 + 1]) end end end SegTree.create = function(self, n, func, emptyvalue) self.func, self.emptyvalue = func, emptyvalue local stagenum, mul = 1, 1 self.stage = {} -- use 1D Tree (stage[], not stage[][]) while mul < n do mul, stagenum = mul * 2, stagenum + 1 end self.stagenum = stagenum for i = 1, mul * 2 - 1 do self.stage[i] = emptyvalue end for i = 1, n do self.stage[mul + i - 1] = i end self:updateAll() end SegTree.update = function(self, idx, force) idx = idx + pow2[self.stagenum] - 1 for i = self.stagenum - 1, 1, -1 do local dst = mfl(idx / 2) local rem = dst * 4 + 1 - idx self.stage[dst] = self.func(self.stage[idx], self.stage[rem]) if not force and self.stage[dst] ~= self.stage[idx] then break end idx = dst end end SegTree.new = function(n, func, emptyvalue) local obj = {} setmetatable(obj, {__index = SegTree}) obj:create(n, func, emptyvalue) return obj end local h, w = io.read("*n", "*n") assert(1 < h and 1 < w) local c_up, c_down, c_right, c_left = io.read("*n", "*n", "*n", "*n") local klim, p = io.read("*n", "*n") local xs, ys = io.read("*n", "*n") local xt, yt = io.read("*n", "*n", "*l") local map = {} for i = 1, h do local s = io.read() map[i] = {} for j = 1, w do map[i][j] = s:sub(j, j) end end local n = h * w local inf = klim + 1 local len = {} local asked = {} for i = 1, n do len[i] = inf asked[i] = false end local spos = (xs - 1) * w + ys len[spos] = 0 asked[n + 1] = true local function mergefunc(x, y) if asked[x] then return y elseif asked[y] then return x else return len[x] < len[y] and x or y end end local st = SegTree.new(n, mergefunc, n + 1) local function walk(src, dst) local dst_row = mce(dst / w) local dst_col = dst - (dst_row - 1) * w local cost = 0 if src + 1 == dst then cost = c_right elseif src - 1 == dst then cost = c_left elseif src + w == dst then cost = c_down elseif src - w == dst then cost = c_up else assert(false) end if map[dst_row][dst_col] == "#" then return end if map[dst_row][dst_col] == "@" then cost = cost + p end if len[src] + cost < len[dst] then len[dst] = len[src] + cost st:update(dst) end end for i = 1, n do local src = st.stage[1] if asked[src] then break end if inf <= len[src] then break end asked[src] = true st:update(src, true) if src % w ~= 1 then walk(src, src - 1) end if src % w ~= 0 then walk(src, src + 1) end if w < src then walk(src, src - w) end if src <= (h - 1) * w then walk(src, src + w) end end local tpos = (xt - 1) * w + yt print(len[tpos] <= klim and "Yes" or "No")