空间站下层区的深空当铺里,乔·王尔德盯着一面旧展示墙发愁。墙上空出来的格子要重新贴满他收藏的旧邮票,可这活儿没那么简单。
这面墙可以看成一个 m × n 的二进制矩阵 grid:0 表示这个格子是空的,1 表示这个格子已经被货物占据。王尔德手里只有一种邮票,尺寸为 stampHeight × stampWidth。
贴邮票要同时满足以下限制与要求:
王尔德敲了敲柜台:「能贴满吗?」如果存在满足上述全部要求的贴法,输出 YES;否则输出 NO。
第一行两个整数 m、n,表示矩阵的行数与列数。
第二行两个整数 stampHeight、stampWidth,表示邮票的高与宽。
接下来 m 行,每行 n 个整数(0 或 1),相邻整数用一个空格隔开,描述矩阵 grid。
一行一个字符串:如果能够贴满所有空格,输出 YES,否则输出 NO。
5 4 4 3 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
YES
对所有测试数据,1 ≤ m, n ≤ 10^5,1 ≤ m × n ≤ 10^6,1 ≤ stampHeight, stampWidth ≤ 10^5,矩阵 grid 中只会出现 0 和 1。