#P0004. 洗澡

洗澡

题目描述

作为远近闻名的大聪明,Waylon 面临着一个严峻的挑战,那就是,洗澡!他努力每天洗澡,但尽管他尽了最大努力,却总是遇到困难。他需要花 ss 分钟洗澡,而一天只有 mm 分钟!

他已经为一天安排了 nn 项任务。任务 ii 表示为一个时间间隔 (li(l_i , ri)r_i) ,这意味着 Waylon 很忙,不能在这个时间间隔内(严格来说是在 lil_i 和 rir_i 之间的任意时间点)洗澡。同时由于 Waylon 真的很擅长安排时间,没有两项任务的时间会发生重叠。

给定所有的 nn 个任务的时间安排,Alex当天能洗澡吗?换句话说,Waylon 是否有一个长度至少为 ss 的空闲时间间隔?

在第一个测试案例中,Waylon 可以在一天的前 33 分钟洗澡,并且不会错过任何任务。

输入格式

第一行包含一个整数 tt ( 1≤t≤1041 \leq t \leq 10^4 ) - 测试用例数。

每个测试用例的第一行包含三个整数 nn 、 ss 和 mm ( 1≤n≤2⋅1051 \leq n \leq 2 \cdot 10^5 ; 1≤s,m≤1091 \leq s, m \leq 10^9 )--即Alex已经计划好的时间间隔数、Waylon 洗澡的时间以及一天的分钟数。

接着是 nn 行,其中的 ii 行包含两个整数 lil_i 和 rir_i ( 0≤li<ri≤m0 \leq l_i < r_i \leq m ),表示第 ii 个任务的时间安排。数据保证没有两个任务时间重叠,且当 i>1i > 1 时,满足 li>ri−1l_i > r_{i-1}。

数据保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5 。

输出格式

对于每个测试用例,如果 Waylon 在该测试用例的情况下可以洗澡,则输出 "YES"(不带引号),否则输出 "NO"(也不带引号)。

每个测试用例的结果之间以换行隔开。

样例 #1

样例输入 #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