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;
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define pb push_back
typedef long long ll;
typedef pair<ll,ll>P;
#define fi first
#define sc second
#define mp make_pair
int x[11][11],n,m,k,s,dep;
bool ok = 0;
void dfs(){
	int rui[11][11]={},rui2[11][11]={}; int pre = 0;
	for(int i=1;i<=n;i++){pre = 0; for(int j=1;j<=m;j++){
		rui[i][j] = rui[i][j-1]+x[i][j];
		if(rui[i][j]-pre > s){
			if(dep == k) return;
			for(int k=1;k<=j;k++){
				x[i][k]*=-1; dep++; dfs(); dep--; x[i][k]*=-1;
				
			}return;
		}
		pre = min(pre,rui[i][j]);
	}}
	for(int j=1;j<=m;j++){pre=0; for(int i=1;i<=n;i++){
		rui2[i][j] = rui2[i-1][j]+x[i][j];
		if(rui2[i][j]-pre > s){
			if(dep == k) return;
			for(int k=1;k<=i;k++){
				x[k][j]*=-1; dep++; dfs(); dep--; x[k][j]*=-1;
				
			}return;
		}
		pre = min(pre,rui2[i][j]);
	}}
	//repn(i,n){repn(j,m)cout<<x[i][j]<<" ";cout<<endl;}
	ok=1; return;
}
int main(){
	cin>>n>>m>>k>>s;
	repn(i,n)repn(j,m)cin>>x[i][j];
	dfs();
	puts(ok?"Yes":"No");
}