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 int long long
#define REP(i, n) for (int i = 0; i < (n); i++)

using vi = vector<int>;
using vvi = vector<vi>;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, K, sum;
    cin >> n >> m >> K >> sum;
    vvi a(n, vi(m));
    REP(i, n) { REP(j, m) cin >> a[i][j]; }

    auto cnt_min = [&](const vi& p) {
        int n = p.size();
        int mi = 100;
        REP(S, 1 << n) {
            int mi_val = 0, acc = 0;
            bool ok = true;
            REP(i, n) {
                int tmp = p[i];
                if (S >> i & 1) tmp = -abs(tmp);
                acc += tmp;
                if (acc - mi_val > sum) {
                    ok = false;
                    break;
                }
                mi_val = min(mi_val, acc);
            }
            if (ok) mi = min(mi, (int)__builtin_popcount(S));
        }
        return mi;
    };
    vi rows, cols;
    REP(i, n) {
        if (cnt_min(a[i]) > 0) rows.push_back(i);
    }
    REP(j, m) {
        vi tmp;
        REP(i, n) tmp.push_back(a[i][j]);
        if (cnt_min(tmp) > 0) cols.push_back(j);
    }

    int H = rows.size(), W = cols.size();
    if (H > K || W > K) {
        cout << "No" << endl;
        return 0;
    }

    vvi row_tbl(H, vi(1 << W));
    REP(i, H) {
        vi vec;
        REP(j, m) vec.push_back(a[rows[i]][j]);
        REP(S, 1 << W) {
            vi tmp = vec;
            REP(j, W) {
                int j_ = cols[j];
                if (S >> j & 1) tmp[j_] = -abs(tmp[j_]);
            }
            row_tbl[i][S] = cnt_min(tmp);
        }
    }
    vvi col_tbl(W, vi(1 << H));
    REP(j, W) {
        vi vec;
        REP(i, n) vec.push_back(a[i][cols[j]]);
        REP(S, 1 << H) {
            vi tmp = vec;
            REP(i, H) {
                int i_ = rows[i];
                if (S >> i & 1) tmp[i_] = -abs(tmp[i_]);
            }
            col_tbl[j][S] = cnt_min(tmp);
        }
    }

    // if (H == 0 && W == 0)
    for (int num = 0; num <= K; num++) {
        vector<int> perm(H * W);
        REP(i, min(num, H * W)) perm[i] = 1;
        sort(perm.begin(), perm.end());
        do {
            int acc = 0;
            REP(i, H) {
                int S = 0;
                REP(j, W) { S |= perm[i * W + j] << j; }
                acc += row_tbl[i][S];
            }
            REP(j, W) {
                int S = 0;
                REP(i, H) { S |= perm[i * W + j] << j; }
                acc += col_tbl[j][S];
            }
            if (acc + num <= K) {
                cout << "Yes" << endl;
                return 0;
            }
        } while (next_permutation(perm.begin(), perm.end()));
    }
    cout << "No" << endl;
}