Problem: You received a card at a banquet. On the card, a matrix of $N$ rows and $M$ columns and two integers $K$ and $S$ are written. All the elements in the matrix are integers, and an integer at the $i$-th row from the top and the $j$-th column from the left is denoted by $A_{i,j}$.

You can select up to $K$ elements from the matrix and invert the sign of the elements. If you can make a matrix such that there is no vertical or horizontal contiguous subsequence whose sum is greater than $S$, you can exchange your card for a prize.

Your task is to determine if you can exchange a given card for a prize.



Input

The input consists of a single test case of the following form.


$N$ $M$ $K$ $S$
$A_{1,1}$ $A_{1,2}$ ... $A_{1,M}$
:
$A_{N,1}$ $A_{N,2}$ ... $A_{N,M}$


The first line consists of four integers $N, M, K$ and $S$ ($1 \leq N, M \leq 10, 1 \leq K \leq 5, 1 \leq S \leq 10^6$). The following $N$ lines represent the matrix in your card. The ($i+1$)-th line consists of $M$ integers $A_{i,1}, A_{i,2}, ..., A_{i, M}$ ($-10^5 \leq A_{i,j} \leq 10^5$).

Output

If you can exchange your card for a prize, print 'Yes'. Otherwise, print 'No'.

Examples

Input

3 3 2 10
5 3 7
2 6 1
3 4 1


Output

Yes


Input

2 3 1 5
4 8 -2
-2 -5 -3


Output

Yes


Input

2 3 1 5
9 8 -2
-2 -5 -3


Output

No


Input

2 2 3 100
0 0
0 0


Output

Yes

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
  int N, M, K, S, A[10][10];
 
  cin >> N >> M >> K >> S;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < M; j++) {
      cin >> A[i][j];
    }
  }
 
  int v[11] = {}, r[11] = {};
 
  auto getCol = [&](int x)
  {
    for(int i = 0; i < N; i++) v[i + 1] = A[i][x] + v[i];
    r[N] = v[N];
    for(int i = N - 1; i >= 0; i--) r[i] = max(r[i + 1], v[i + 1]);
    int ret = 0;
    for(int i = 0; i < N; i++) ret = max(ret, r[i] - v[i]);
    return (ret);
  };
 
 
  auto getRow = [&](int y)
  {
    for(int i = 0; i < M; i++) v[i + 1] = A[y][i] + v[i];
    r[M] = v[M];
    for(int i = M - 1; i >= 0; i--) r[i] = max(r[i + 1], v[i + 1]);
    int ret = 0;
    for(int i = 0; i < M; i++) ret = max(ret, r[i] - v[i]);
    return (ret);
  };
 
 
  int a = 0, b = 0;
  vector< int > latte, malta;
  for(int i = 0; i < M; i++) {
    if(getCol(i) > S) ++a, latte.emplace_back(i);
  }
  for(int i = 0; i < N; i++) {
    if(getRow(i) > S) ++b, malta.emplace_back(i);
  }
 
  if(a > K || b > K) {
    cout << "No" << endl;
    return (0);
  }
 
  vector< pair< int, int > > vs;
  for(int i = 0; i < M; i++) {
    if(getCol(i) > S) for(int j = 0; j < N; j++) vs.emplace_back(j, i);
  }
  for(int i = 0; i < N; i++) {
    if(getRow(i) > S) for(int j = 0; j < M; j++) vs.emplace_back(i, j);
  }
  sort(begin(vs), end(vs));
  vs.erase(unique(begin(vs), end(vs)), end(vs));
 
  int dep = 0;
  function< bool(int, int) > dfs = [&](int idx, int sz)
  {
    ++dep;
    if(dep >= 1145141) {
      cout << "No" << endl;
      exit(0);
    }
    if(idx == vs.size()) {
      for(int i : latte) if(getCol(i) > S) return (false);
      for(int i : malta) if(getRow(i) > S) return (false);
      return (true);
    }
    for(int i : malta) {
      if(vs[idx].first <= i) break;
      if(getRow(i) > S) return (false);
    }
    if(sz + 1 <= K) {
      if(A[vs[idx].first][vs[idx].second] > 0) {
        A[vs[idx].first][vs[idx].second] *= -1;
        if(dfs(idx + 1, sz + 1)) return (true);
        A[vs[idx].first][vs[idx].second] *= -1;
      }
    }
    return (dfs(idx + 1, sz));
  };
 
 
  if(dfs(0, 0)) cout << "Yes" << endl;
  else cout << "No" << endl;
}