MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 16px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

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}$ $\\cdots$ $A\_{1,M}$ $\\vdots$ $A\_{N,1}$ $A\_{N,2}$ $\\cdots$ $A\_{N,M}$

The first line consists of four integers $N$, $M$, $K$, and $S$ ($1 \\le N, M \\le 10$, $1 \\le K \\le 5$, $1 \\le S \\le 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}$, $\\ldots$, $A\_{i,M}$ ($-10^5 \\le A\_{i,j} \\le 10^5$).

Output

If you can exchange your card for a prize, print Yes. Otherwise, print No.

Sample Input 1

3 3 2 10
5 3 7
2 6 1
3 4 1

Output for Sample Input 1

Yes

The sum of a horizontal contiguous subsequence from $A\_{1,1}$ to $A\_{1,3}$ is $15$. The sum of a vertical contiguous subsequence from $A\_{1,2}$ to $A\_{3,2}$ is $13$. If you flip the sign of $A\_{1,2}$, there is no vertical or horizontal contiguous subsequence whose sum is greater than $S$.

Sample Input 2

2 3 1 5
4 8 -2
-2 -5 -3

Output for Sample Input 2

Yes

Sample Input 3

2 3 1 5
9 8 -2
-2 -5 -3

Output for Sample Input 3

No

Sample Input 4

2 2 3 100
0 0
0 0

Output for Sample Input 4

Yes