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.

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$).

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

3 3 2 10 5 3 7 2 6 1 3 4 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$.

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

Yes

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

No

2 2 3 100 0 0 0 0

Yes

Source: ACM-ICPC Japan Alumni Group Summer Camp 2017
, Tokyo, Japan, 2017-09-24

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/