作为一名计算机科学专业的学生,亚历克斯面临着一项艰巨的挑战——洗澡。他尝试每天洗澡,但尽管他尽了最大努力,但总是遇到挑战。他洗澡需要 $$$s$$$ 分钟,而一天只有 $$$m$$$ 分钟!
他当天已经计划了 $$$n$$$ 任务。任务 $$$i$$$ 表示为一个时间间隔 $$$(l_i$$$, $$$r_i)$$$,这意味着 Alex 很忙,无法在该时间间隔内洗澡(严格在 $$$l_i$$$ 和 $$$r_i$$$ 之间的任何时间点)。没有两个任务重叠。
考虑到所有 $$$n$$$ 时间间隔,Alex 那天能够洗澡吗?换句话说,Alex 是否有至少 $$$s$$$ 长度的空闲时间间隔?
在第一个测试用例中,Alex 可以在当天的前 $$$3$$$ 分钟洗澡,并且不会错过任何任务。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$s$$$ 和 $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq s, m \leq 10^9$$$) - Alex 已经计划的时间间隔数,Alex 采取一个淋浴,以及每天的分钟数。
接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \leq l_i < r_i \leq m$$$) — 第 $$$i$$$ 个任务的时间间隔。没有两个任务重叠。
对输入的附加约束:对于每个 $$$i > 1$$$,$$$l_i > r_{i-1}$$$。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果 Alex 可以为给定的测试用例洗澡,则输出“YES”(不带引号),否则输出“NO”(也不带引号)。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。
示例
输入 #1
4 3 3 10 3 5 6 8 9 10 3 3 10 1 2 3 5 6 7 3 3 10 1 2 3 5 6 8 3 4 10 1 2 6 7 8 9
输出 #1
YES YES NO YES