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;
signed main(){
  int n,m,k,s;
  cin>>n>>m>>k>>s;
  int a[11][11];
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      cin>>a[i][j];

  /*//
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      cout<<a[i][j]<<" \n"[j==m-1]<<flush;
  //*/  

  auto row=[&](int i){
    int x[m+1];
    x[0]=0;
    for(int j=0;j<m;j++) x[j+1]=x[j]+a[i][j];
    int y[m+1];
    y[m]=x[m];
    for(int j=m-1;j>=0;j--)
      y[j]=max(y[j+1],x[j+1]);
    int res=0;
    for(int j=0;j<m;j++)
      res=max(res,y[j]-x[j]);

    //cout<<i<<":i"<<endl;for(int j=0;j<=m;j++) cout<<j<<":"<<x[j]<<" "<<y[j]<<":"<<a[i][j]<<endl;
    
    return res;
  };
  
  auto col=[&](int j){
    int x[n+1];
    x[0]=0;
    for(int i=0;i<n;i++) x[i+1]=x[i]+a[i][j];
    int y[n+1];
    y[n]=x[n];
    for(int i=n-1;i>=0;i--)
      y[i]=max(y[i+1],x[i+1]);
    int res=0;
    for(int i=0;i<n;i++)
      res=max(res,y[i]-x[i]);
    return res;
  };

  vector<int> vx,vy;
  for(int i=0;i<n;i++){
    //cout<<row(i)<<endl;
    if(row(i)>s) vy.push_back(i);
  }
  for(int j=0;j<m;j++){
    //cout<<col(j)<<endl;
    if(col(j)>s) vx.push_back(j);
  }
  if((int)vx.size()>k||(int)vy.size()>k){
    cout<<"No"<<endl;
    return 0;
  }

  int ans=0;
  function<void(int,int,int)> dfs=
    [&](int b,int c,int d){
    {
      int tmp=0;
      for(int i=0;i<n;i++){
	tmp|=row(i)>s;
	if(tmp) break;
      }
      for(int j=0;j<m;j++){
	tmp|=col(j)>s;
	if(tmp) break;
      }
      if(!tmp){
	ans=1;
	return;
      }
    }
    if(b==k) return;
    for(int i=c;i<(int)vy.size();i++){
      for(int j=(i==c?d+1:0);j<m;j++){
	if(a[vy[i]][j]<=0) continue;
	a[vy[i]][j]*=-1;
	dfs(b+1,i,j);
	a[vy[i]][j]*=-1;
	if(ans) return;
      }
    }
  };
  
  function<void(int,int,int)> dfs2=
    [&](int b,int c,int d){
    {
      int tmp=0;
      for(int i=0;i<n;i++){
	tmp|=row(i)>s;
	if(tmp) break;
      }
      for(int j=0;j<m;j++){
	tmp|=col(j)>s;
	if(tmp) break;
      }
      if(!tmp){
	ans=1;
	return;
      }
    }
    if(b==k) return;
    for(int j=c;j<(int)vx.size();j++){
      for(int i=(j==c?d+1:0);i<n;i++){
	if(a[i][vx[j]]<=0) continue;
	a[i][vx[j]]*=-1;
	dfs2(b+1,j,i);
	a[i][vx[j]]*=-1;
	if(ans) return;
      }
    }
  };
  dfs(0,0,0);
  dfs2(0,0,0);
  //assert(!ans);
  cout<<(ans?"Yes":"No")<<endl;
  return 0;
}