问题描述

你在一个宴会上收到了一张卡片。卡片上写着一个 $N$ 行 $M$ 列的矩阵以及两个整数 $K$ 和 $S$。矩阵中的所有元素都是整数，第 $i$ 行从上往下数第 $j$ 列的整数用 $A\_{i,j}$ 表示。

你可以从矩阵中选择最多 $K$ 个元素并改变这些元素的符号。如果你可以得到一个满足条件的矩阵，即不存在连续的垂直或水平子序列使得其和大于 $S$，那么你就可以用这张卡片换取奖品。

你的任务是确定是否可以用给定的卡片换取奖品。

输入

输入包含一个测试用例，格式如下：

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

第一行包含四个整数 $N$、$M$、$K$ 和 $S$ ($1 \le N, M \le 10$, $1 \le K \le 5$, $1 \le S \le 10^6$)。接下来的 $N$ 行表示卡片上的矩阵。第 $(i+1)$ 行由 $M$ 个整数 $A\_{i,1}$、$A\_{i,2}$、$\ldots$、$A\_{i,M}$ ($-10^5 \le A\_{i,j} \le 10^5$) 组成。

输出

如果你可以用这张卡片换取奖品，则输出 Yes。否则，输出 No。

示例输入 1

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

示例输出 1

Yes

水平连续子序列从 $A\_{1,1}$ 到 $A\_{1,3}$ 的和为 $15$。垂直连续子序列从 $A\_{1,2}$ 到 $A\_{3,2}$ 的和为 $13$。如果你改变 $A\_{1,2}$ 的符号，就不会存在水平或垂直的连续子序列使得其和大于 $S$。

示例输入 2

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

示例输出 2

Yes

示例输入 3

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

示例输出 3

No

示例输入 4

2 2 3 100
0 0
0 0

示例输出 4

Yes