#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int r,c,s;
int a[10][10];
bool ok = false;

void dfs(int d){
    if(d == -1) return;
    bool found = false;

    // printf(" ----d %d\n",d);
    // rep(i,r){
    //     rep(j,c) printf(" %d",a[i][j]);
    //     printf("\n");
    // }

    rep(i,r){
        rep(j,c){
            int z = 0;
            for(int k=j; k<c; ++k){
                z += a[i][k];
                if(z>s) found = true;
            }
        }

        if(found){
            rep(j,c){
                a[i][j] = -a[i][j];
                dfs(d-1);
                a[i][j] = -a[i][j];
            }
            break;
        }
    }

    if(!found){
        rep(i,c){
            rep(j,r){
                int z = 0;
                for(int k=j; k<r; ++k){
                    z += a[k][i];
                    if(z>s) found = true;
                }
            }

            if(found){
                rep(j,r){
                    a[j][i] = -a[j][i];
                    dfs(d-1);
                    a[j][i] = -a[j][i];
                }
                break;
            }
        }
    }

    if(!found) ok = true;
}

int main(){
    int K;
    cin >>r >>c >>K >>s;
    rep(i,r)rep(j,c) cin >>a[i][j];

    dfs(K);
    cout << (ok?"Yes":"No") << endl;
    return 0;
}


### Prompt

Your task is to create a cpp solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int r,c,s;
int a[10][10];
bool ok = false;

void dfs(int d){
    if(d == -1) return;
    bool found = false;

    // printf(" ----d %d\n",d);
    // rep(i,r){
    //     rep(j,c) printf(" %d",a[i][j]);
    //     printf("\n");
    // }

    rep(i,r){
        rep(j,c){
            int z = 0;
            for(int k=j; k<c; ++k){
                z += a[i][k];
                if(z>s) found = true;
            }
        }

        if(found){
            rep(j,c){
                a[i][j] = -a[i][j];
                dfs(d-1);
                a[i][j] = -a[i][j];
            }
            break;
        }
    }

    if(!found){
        rep(i,c){
            rep(j,r){
                int z = 0;
                for(int k=j; k<r; ++k){
                    z += a[k][i];
                    if(z>s) found = true;
                }
            }

            if(found){
                rep(j,r){
                    a[j][i] = -a[j][i];
                    dfs(d-1);
                    a[j][i] = -a[j][i];
                }
                break;
            }
        }
    }

    if(!found) ok = true;
}

int main(){
    int K;
    cin >>r >>c >>K >>s;
    rep(i,r)rep(j,c) cin >>a[i][j];

    dfs(K);
    cout << (ok?"Yes":"No") << endl;
    return 0;
}


```