Low Range-Sum Matrix

Time limit2sMemory limit512 MB

Summary

Flip signs of at most K cells in an N by M matrix (both at most 10) so that no horizontal or vertical contiguous segment sums to more than S.

Level: Hard9 of 10
Topics: Brute force, Dynamic programming, Bit manipulation, Implementation
Solved: No attempts yet

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}$ $\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.

Examples4

Example 1
Input
```
3 3 2 10
5 3 7
2 6 1
3 4 1
```
Expected output
```
Yes
```
Example 2
Input
```
2 3 1 5
4 8 -2
-2 -5 -3
```
Expected output
```
Yes
```
Example 3
Input
```
2 3 1 5
9 8 -2
-2 -5 -3
```
Expected output
```
No
```
Example 4
Input
```
2 2 3 100
0 0
0 0
```
Expected output
```
Yes
```