All Tracks Algorithms Sorting Bubble Sort Problem

Benny and Segments

Sorting, Two pointer


View Russian Translation

One day Benny was walking and realized that her life was boring. Everything was grey, even roads in the best park were grey.

Therefore she decided to make roads a little bit brighter. She know that every road in the park is a segment laying on the X axis with coordinates Xl, Xr (Xl ≤ Xr). Roads may intersect or overlap.

She chooses any subset of roads and paints them in red. After that she wants to get one continuous red segment. As she really likes number L the length of this segment has to be equal to L.

Your task is to determine if it is possible to choose some subset of roads and paint them to get one red segment with the length equal to L?

If it's possible print in a single line "Yes"(without quotes), otherwise print "No" (without quotes).

Input format

The first line contains one integer T - the number of test cases. Each test case starts with two integers N and L, denoting the number of roads and Benny's favorite number L. The next N lines contain two integers Xl, Xr, denoting the left and right borders of the road.

Output format

For every test case output "Yes" if it is possible to paint some roads and "No" otherwise.


  • 1 ≤ sum of all N ≤ 2 * 103
  • 1 ≤ L ≤ 106
  • 1 ≤ Xl ≤ Xr ≤ 106
  • 1 ≤ N ≤ 20, 1 ≤ Xl ≤ Xr ≤ 200, holds for test cases worth 10% of the problem's score.
  • 1 ≤ N ≤ 100, 1 ≤ Xl ≤ Xr ≤ 200, holds for test cases worth 20% of the problem's score.

Sample Explanation

In the first test case you can choose roads (1; 2) (2; 3) and (3; 4) the result segment is (1; 4) and its length equals 3 (4 - 1 = 3).

In the second case you can not choose any subset that will create segment with the length equal to 4.

5 3
1 2
2 3
3 4
1 5
2 6
2 3
1 2
2 6
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications