题目描述

有 $N$ 个特殊的拼图块。每个拼图块由三个宽度为 $1$、高度不小于 $1$ 的矩形拼接而成。第 $i$ 个拼图块的构造如下：

• 以高度为 $H$ 的矩形块为中间部分，将高度为 $A_i$ 的矩形块连接在左侧，高度为 $B_i$ 的矩形块连接在右侧。其中，左侧矩形块底边比中间矩形块底边高 $C_i$，右侧矩形块底边比中间矩形块底边高 $D_i$。

Sune君想把这些拼图块放在一个边长为 $10^{100}$ 的正方形桌子上。此时需要满足以下条件：

• 必须把所有拼图块都放在桌子上。
• 每个拼图块的中间部分底边都要与桌子的前边缘接触。
• 左右两侧的矩形块的底边要么与桌子的前边缘接触，要么与其他某个拼图块的某部分的上边缘完全接触。
• 不能旋转或翻转拼图块。

请判断是否存在一种满足条件的排放方法。

输入格式

输入按以下格式由标准输入给出：

$N$ $H$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ : $A_N$ $B_N$ $C_N$ $D_N$

输出格式

如果存在一种满足条件的拼图块排列方式，输出 YES；否则输出 NO。

样例 1

输入

3 4
1 1 0 0
2 2 0 1
3 3 1 0

输出

YES

样例 2

输入

4 2
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1

输出

NO

样例 3

输入

10 4
1 1 0 3
2 3 2 0
1 2 3 0
2 1 0 0
3 2 0 2
1 1 3 0
3 2 0 0
1 3 2 0
1 1 1 3
2 3 0 0

输出

YES

说明/提示

范围

• $1\leq N\leq 100000$
• $1\leq H\leq 200$
• $1\leq A_i\leq H$
• $1\leq B_i\leq H$
• $0\leq C_i\leq H-A_i$
• $0\leq D_i\leq H-B_i$
• 所有输入均为整数。

样例解释 1

例如，可以按下图方式进行放置。

由 ChatGPT 5 翻译