问题陈述
您在宴会上收到了一张卡片。卡片上写有 $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