ndungeon_21576
Nikhil has designed the following game. The game is played in a
set of rooms in a dungeon, arranged in an M × N
rectangular grid. In one of the rooms, the evil wazir has imprisoned
the princess. The noble prince is on his way to rescue the
princess.
The prince starts in the room at the top left corner of the grid,
which is labelled (1,1).  Each room contains some guards.  It takes a
certain amount of time before the prince can kill all the guards in
the room he is in.  The time taken to kill the guards varies from room
to room.  Once he has killed all the guards in a room, he can move on
to any one of its neighbours by going left, right, up or down,
provided, of course, that there is a neighbouring room in the
corresponding direction.
The wazir, knowing that the prince is on his way, has set a time
bomb that will kill the princess after T seconds.  You will
be given the position of the princess, the time left for the bomb to
go off and the time it takes for the prince to kill the guards in each
of the rooms in the dungeon.  Your task is to determine if it is
possible for the prince to reach the princess and save her by defusing
the bomb before the T seconds expire.
 For example, suppose the dungeon is described by the following
grid of numbers.
2 3 2
2 5 1
5 3 1
3 1 1

The number at position (i,j) indicates the time taken for
the prince to overpower the guards in room (i,j). Suppose the
princess is in the room at position (4,2). If T = 10.  there
is no way the prince can reach the princess in time. However, if
T = 15, the prince can reach the princess with 4 seconds to
spare, as follows.  Starting from (1,1), he moves right to (1,2) and
then (1,3), comes down all the way to (4,3) and then moves (4,2).  This
takes 11 seconds (note that he must also overpower the guard in the
room where the princess is incarcerated). You can check that he cannot
reach the princess with more than 4 seconds to spare by any route.

Input

The first line contains two integers M and N indicating the number of rows and columns in the rectangular dungeon. Lines 2,3,…,M+1 contain N positive integers. The jth integer on line i+1 is the time taken to overpower the guards at room (i,j). The last line in the input, line M+2, contains three integers a, b and T, where (a,b) is the position of the cell where the princess is held and T is the amount of time before the bomb goes off.



Output

If it is not possible for the prince to save the princess then print a single line with the answer NO. Otherwise, print two lines. The first line should say YES. The second line should contain a single integer indicating the maximum possible time to spare when the prince rescues the princess.



Constraints

You may assume that 1 ≤ N,M ≤ 70.

Example

Input:
4 3 
2 3 2
2 5 1
5 3 1
3 1 1
4 2 15

Output:
YES
4
#!/usr/bin/python
# Richard Lee
# CodeChef
# Nikhils Dungeon
#
import os
import sys

inp = sys.stdin.readline
INF=-1

# what does the board look lke?
l = inp()
p = l.split()
m = int(p[0])
n = int(p[1])
l = ""
for i in xrange(m):
   l += inp()
board = [int(i) for i in l.split()]

# where's the princess and how much time is left?
l = inp()
p = l.split()
a = int(p[0])
b = int(p[1])
T = int(p[2])

# invoke Dijstkra to find the best route
def get_neighbors(i):
   global n
   r = i / n
   c = (i - (r * n)) % n
   n_q = []
   if (r+1 < m):
      n_q.append(((r+1) * n) + c)
   if (r-1 >= 0):
      n_q.append(((r-1) * n) + c)
   if (c+1 < n):
      n_q.append((r * n) + (c+1))
   if (c-1 >= 0):
      n_q.append((r * n) + (c-1))
   return n_q

# Dijstkra is invoking...
d = [INF for i in xrange(m * n)]
qd = [True for i in xrange(m *n)]
qr = [False for i in xrange(m *n)]
d[0] = 0

# stop at princess' location
p_l = ((a - 1) * n) + (b-1)
q = [0]
while len(q) > 0:
   i = q.pop()
   if d[i] == INF or i == p_l:
      break # infinity...
   qd[i] = False
   v_l = get_neighbors(i)   
   for v in v_l:
      if qd[v]:
         alt = d[i] + board[v]
         if d[v] == INF or alt < d[v]:
            d[v] = alt
         if not qr[v]:
            q.append(v)
            qr[v] = True
   q = sorted(q, lambda x,y: d[y] - d[x])
# Dijstkra done invoking...

# can save the princess?
c = d[p_l] + board[0]
if c < T:
   print "YES"
   print T - c
else:
   print "NO"