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>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n,m,k,s;
int a[11][11];
bool flag=false;
int sumx[15][15][15];
int sumy[15][15][15];
vector<int> decx[15];
vector<int> decy[15];

void dfs(int dep,int v,int now){
	if(flag)return;
	if(now>k)return;
	if(decx[dep].size()==0){
		if(decy[dep].size()==0){
			flag=true;
			return;
		}
		if(decy[dep].size()==v){
			decx[dep+1].clear();
			decy[dep+1].clear();
			memset(sumx,0,sizeof(sumx));
			memset(sumy,0,sizeof(sumy));
			for(int i=0;i<n;i++){
				bool flag=false;
				for(int j=0;j<m;j++){
					for(int k=j;k<m;k++){
						sumx[i][j][k+1]+=sumx[i][j][k];
						sumx[i][j][k+1]+=a[i][k];
						if(sumx[i][j][k+1]>s){
							if(!flag)decx[dep+1].push_back(i);
							flag=true;
						}
					}
				}
			}
			for(int i=0;i<m;i++){
				bool flag=false;
				for(int j=0;j<n;j++){
					for(int k=j;k<n;k++){
						sumy[i][j][k+1]+=sumy[i][j][k];
						sumy[i][j][k+1]+=a[k][i];
						if(sumy[i][j][k+1]>s){
							if(!flag)decy[dep+1].push_back(i);
							flag=true;
						}
					}
				}
			}
			if(max((int)decx[dep+1].size(),(int)decy[dep+1].size())<=k-now)dfs(dep+1,0,now);
		}else{
			for(int i=0;i<n;i++){
				a[i][decy[dep][v]]*=-1;
				dfs(dep,v+1,now+1);
				a[i][decy[dep][v]]*=-1;
			}
		}
	}else{
		if(decx[dep].size()==v){
			decx[dep+1].clear();
			decy[dep+1].clear();
			memset(sumx,0,sizeof(sumx));
			memset(sumy,0,sizeof(sumy));
			for(int i=0;i<n;i++){
				bool flag=false;
				for(int j=0;j<m;j++){
					for(int k=j;k<m;k++){
						sumx[i][j][k+1]+=sumx[i][j][k];
						sumx[i][j][k+1]+=a[i][k];
						if(sumx[i][j][k+1]>s){
							if(!flag)decx[dep+1].push_back(i);
							flag=true;
						}
					}
				}
			}
			for(int i=0;i<m;i++){
				bool flag=false;
				for(int j=0;j<n;j++){
					for(int k=j;k<n;k++){
						sumy[i][j][k+1]+=sumy[i][j][k];
						sumy[i][j][k+1]+=a[k][i];
						if(sumy[i][j][k+1]>s){
							if(!flag)decy[dep+1].push_back(i);
							flag=true;
						}
					}
				}
			}
			if(max((int)decx[dep+1].size(),(int)decy[dep+1].size())<=k-now)dfs(dep+1,0,now);
		}else{
			for(int i=0;i<m;i++){
				a[decx[dep][v]][i]*=-1;
				dfs(dep,v+1,now+1);
				a[decx[dep][v]][i]*=-1;
			}
		}
	}
}

int main(void){
	scanf("%d%d%d%d",&n,&m,&k,&s);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j]>s){
				k--;
				a[i][j]*=-1;
			}
		}
	}
	if(k<0){
		printf("No\n");
		return 0;
	}
	for(int i=0;i<n;i++){
		bool flag=false;
		for(int j=0;j<m;j++){
			for(int k=j;k<m;k++){
				sumx[i][j][k+1]+=sumx[i][j][k];
				sumx[i][j][k+1]+=a[i][k];
				if(sumx[i][j][k+1]>s){
					if(!flag)decx[0].push_back(i);
					flag=true;
				}
			}
		}
	}
	for(int i=0;i<m;i++){
		bool flag=false;
		for(int j=0;j<n;j++){
			for(int k=j;k<n;k++){
				sumy[i][j][k+1]+=sumy[i][j][k];
				sumy[i][j][k+1]+=a[k][i];
				if(sumy[i][j][k+1]>s){
					if(!flag)decy[0].push_back(i);
					flag=true;
				}
			}
		}
	}
	if(decx[0].size()>k || decy[0].size()>k){
		printf("No\n");
		return 0;
	}
	dfs(0,0,0);
	printf("%s\n",flag?"Yes":"No");
	return 0;
}