Problem: A dam construction project was designed around an area called Black Force. The area is surrounded by mountains and its rugged terrain is said to be very suitable for constructing a dam.

However, the project is now almost pushed into cancellation by a strong protest campaign started by the local residents. Your task is to plan out a compromise proposal. In other words, you must find a way to build a dam with sufficient capacity, without destroying the inhabited area of the residents.

The map of Black Force is given as H × W cells (0 < H, W ≤ 20). Each cell hi, j is a positive integer representing the height of the place. The dam can be constructed at a connected region surrounded by higher cells, as long as the region contains neither the outermost cells nor the inhabited area of the residents. Here, a region is said to be connected if one can go between any pair of cells in the region by following a sequence of left-, right-, top-, or bottom-adjacent cells without leaving the region. The constructed dam can store water up to the height of the lowest surrounding cell. The capacity of the dam is the maximum volume of water it can store. Water of the depth of 1 poured to a single cell has the volume of 1.

The important thing is that, in the case it is difficult to build a sufficient large dam, it is allowed to choose (at most) one cell and do groundwork to increase the height of the cell by 1 unit. Unfortunately, considering the protest campaign, groundwork of larger scale is impossible. Needless to say, you cannot do the groundwork at the inhabited cell.

Given the map, the required capacity, and the list of cells inhabited, please determine whether it is possible to construct a dam.



Input

The input consists of multiple data sets. Each data set is given in the following format:


H W C R
h1,1 h1,2 . . . h1,W
...
hH,1 hH,2 . . . hH,W
y1 x1
...
yR xR


H and W is the size of the map.  is the required capacity. R (0 < R < H × W) is the number of cells inhabited. The following H lines represent the map, where each line contains W numbers separated by space. Then, the R lines containing the coordinates of inhabited cells follow. The line “y x” means that the cell hy,x is inhabited.

The end of input is indicated by a line “0 0 0 0”. This line should not be processed.

Output

For each data set, print “Yes” if it is possible to construct a dam with capacity equal to or more than C. Otherwise, print “No”.

Example

Input

4 4 1 1
2 2 2 2
2 1 1 2
2 1 1 2
2 1 2 2
1 1
4 4 1 1
2 2 2 2
2 1 1 2
2 1 1 2
2 1 2 2
2 2
4 4 1 1
2 2 2 2
2 1 1 2
2 1 1 2
2 1 1 2
1 1
3 6 6 1
1 6 7 1 7 1
5 1 2 8 1 6
1 4 3 1 5 1
1 4
5 6 21 1
1 3 3 3 3 1
3 1 1 1 1 3
3 1 1 3 2 2
3 1 1 1 1 3
1 3 3 3 3 1
3 4
0 0 0 0


Output

Yes
No
No
No
Yes

Solution (in CPP):

Solution:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_H = 20;
const int MAX_W = 20;
const int MAX_R = MAX_H * MAX_W;
const int INF = 1 << 30;

const int dxs[] = { 1, 0, -1, 0};
const int dys[] = { 0, -1, 0, 1};
  
/* typedef */

typedef vector<int> vi;
typedef pair<int,int> pii;

/* global variables */

int h, w, c, r;
int hgts[MAX_H][MAX_W];
pii ihpts[MAX_R];
bool ihbs[MAX_H][MAX_W], rgs[MAX_H][MAX_W], used[MAX_H][MAX_W];
int nrg;

/* subroutines */

void ngrgs(int y0, int x0) {
  if (! rgs[y0][x0]) return;
  queue<pii> q;
  q.push(pii(y0, x0));
  rgs[y0][x0] = false;
  nrg--;
  
  while (! q.empty()) {
    pii u = q.front(); q.pop();
    int& uy = u.first;
    int& ux = u.second;
    int uh = hgts[uy][ux];
    for (int di = 0; di < 4; di++) {
      int vy = uy + dys[di];
      int vx = ux + dxs[di];
      if (vy >= 0 && vy < h && vx >= 0 && vx < w &&
	  rgs[vy][vx] && hgts[vy][vx] >= uh) {
	rgs[vy][vx] = false;
	nrg--;
	q.push(pii(vy, vx));
      }
    }
  }
}

bool dam() {
  nrg = w * h;
  memset(rgs, true, sizeof(rgs));

  for (int y0 = 0; y0 < h; y0++) {
    ngrgs(y0, 0);
    ngrgs(y0, w - 1);
  }
  for (int x0 = 0; x0 < w; x0++) {
    ngrgs(0, x0);
    ngrgs(h - 1, x0);
  }

  for (int i = 0; i < r; i++)
    ngrgs(ihpts[i].first, ihpts[i].second);
  
  if (false) {
    for (int y = 0; y < h; y++) {
      for (int x = 0; x < w; x++) cout << rgs[y][x];
      cout << endl;
    }
  }

  while (nrg) {
    int y0 = 0, x0 = 0;
    while (! rgs[y0][x0]) 
      if (++x0 >= w) x0 = 0, y0++;

    int min_wl = INF, y1, x1;
    memset(used, false, sizeof(used));
    used[y0][x0] = true;
    queue<pii> q;
    q.push(pii(y0, x0));

    while (! q.empty()) {
      pii u = q.front(); q.pop();
      int& uy = u.first;
      int& ux = u.second;
      for (int di = 0; di < 4; di++) {
	int vy = uy + dys[di];
	int vx = ux + dxs[di];
	if (! rgs[vy][vx]) {
	  if (min_wl > hgts[vy][vx]) {
	    min_wl = hgts[vy][vx];
	    y1 = uy, x1 = ux;
	  }
	}
	else if (! used[vy][vx]) {
	  used[vy][vx] = true;
	  q.push(pii(vy, vx));
	}
      }
    }

    int wv = min_wl - hgts[y1][x1];
    memset(used, false, sizeof(used));
    used[y1][x1] = true;
    queue<pii> q0;
    q0.push(pii(y1, x1));

    while (! q0.empty()) {
      pii u = q0.front(); q0.pop();
      int& uy = u.first;
      int& ux = u.second;
      for (int di = 0; di < 4; di++) {
	int vy = uy + dys[di];
	int vx = ux + dxs[di];
	if (rgs[vy][vx] && ! used[vy][vx] && min_wl > hgts[vy][vx]) {
	  wv += min_wl - hgts[vy][vx];
	  used[vy][vx] = true;
	  q0.push(pii(vy, vx));
	}
      }
    }

    //printf("wv=%d\n", wv);
    if (wv >= c) return true;

    ngrgs(y1, x1);
  }

  return false;
}

/* main */

int main() {
  for (;;) {
    cin >> h >> w >> c >> r;
    if (h == 0) break;

    for (int y = 0; y < h; y++)
      for (int x = 0; x < w; x++) cin >> hgts[y][x];

    memset(ihbs, false, sizeof(ihbs));
    for (int i = 0; i < r; i++) {
      int y, x;
      cin >> y >> x;
      y--, x--;
      ihpts[i].first = y;
      ihpts[i].second = x;
      ihbs[y][x] = true;
    }

    bool ok = dam();

    for (int y = 0; ! ok && y < h; y++)
      for (int x = 0; ! ok && x < w; x++)
	if (! ihbs[y][x]) {
	  hgts[y][x]++;
	  ok = dam();
	  //printf("(%d,%d)=%d\n", y, x, ok);
	  hgts[y][x]--;
	}

    cout << (ok ? "Yes" : "No") << endl;
  }

  return 0;
}