#P14504. [2026年省队模拟联测]segment

[2026年省队模拟联测]segment

题目描述

给定一条数轴,数轴上有若干区间。你需要在每一个区间中选出一个长度为 tt 的子区间。

你要保证使得这些子区间两两无交。(端点重合不算有交)

请问你能否做到这一点。

输入格式

本题多测。第一行输入数据组数 TT。

对于每组数据。输入的第一行包含两个整数 n(1≤n≤104)n (1 \le n \le 10^{4}) 和 t(1≤t≤105)t (1 \le t \le 10^{5}),其中 nn 是区间数量,tt 是你要选出的子区间长度。

接下来的 nn 行中,每行描述了一个区间。每行包含两个非负整数 aa 和 bb,其中 aa 是可以开始拍摄该照片的最早时间,bb 是必须完成拍摄的时间,满足 a+t≤b≤109a + t \le b \le 10^{9}。

输出格式

输出共 TT 行。

对于每组数据。

如果可能做到,则输出 yes,否则输出 no。

输入输出样例 #1

输入 #1

3
2 10
0 15
5 20
2 10
1 15
0 20
2 10
5 30
10 20

输出 #1

yes
no
yes

对于 5%5\% 的数据,n≤10n \le 10。

对于 15%15\% 的数据,n≤100n \le 100。

对于 25%25\% 的数据,n≤500n \le 500。

对于 100%100\% 的数据,n≤1000n \le 1000。