import std.algorithm, std.array, std.container, std.range, std.bitmanip; import std.numeric, std.math, std.bigint, std.random; import std.string, std.conv, std.stdio, std.typecons; struct point { int x; int y; point opBinary(string op)(point rhs) { static if (op == "+") return point(x + rhs.x, y + rhs.y); else static if (op == "-") return point(x - rhs.x, y - rhs.y); } } const auto sibPoints = [point(-1, 0), point(0, -1), point(1, 0), point(0, 1)]; struct pointWeight { point p; int weight; int opCmp(pointWeight rhs) { return weight == rhs.weight ? 0 : (weight < rhs.weight ? -1 : 1); } } void main() { auto rd = readln.split.map!(to!int); auto n = rd[0], v = rd[1], o = point(rd[2] - 1, rd[3] - 1); auto lij = iota(n).map!(_ => readln.split.map!(to!int).array).array; auto s = point(0, 0), e = point(n - 1, n - 1); auto dummy = point(-1, -1); auto r1 = dijkstra(n, lij, s, e, o); if (v - r1 > 0) { writeln("YES"); } else { if (o == dummy) { writeln("NO"); } else { auto r2 = dijkstra(n, lij, s, o, dummy); auto r3 = dijkstra(n, lij, o, e, dummy); if ((v - r2) * 2 - r3 > 0) writeln("YES"); else writeln("NO"); } } } int dijkstra(int n, int[][] lij, point s, point e, point o) { auto memo = new int[][](n, n); memo.each!((a) { a[] = -1; }); memo[s.y][s.x] = 0; auto pi = heapify!("a > b")(Array!pointWeight()); void addPointWeight(pointWeight pw) { bool valid(point p) { return p.x >= 0 && p.x < n && p.y >= 0 && p.y < n; } auto p = pw.p, w = pw.weight; foreach (sib; sibPoints) { auto np = p + sib; if (!valid(np) || np == o) continue; auto nw = w + lij[np.y][np.x]; if (memo[np.y][np.x] < 0 || nw < memo[np.y][np.x]) { memo[np.y][np.x] = nw; pi.insert(pointWeight(np, nw)); } } } addPointWeight(pointWeight(s, 0)); while (!pi.empty) { auto pw = pi.front, p = pw.p, w = pw.weight; pi.removeFront; if (p == e) return w; addPointWeight(pw); } return 0; }