Scenery 2

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 사진마다 촬영 가능한 구간 [a, b]와 촬영 시간 t가 주어질 때, 모든 사진을 겹치지 않게 찍을 수 있는지 판단합니다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 힙
정답자: 아직 제출이 없습니다

문제

Images by John Fowler, Carol Highsmith, and Richard Woodland

라피드시티 여행 중 하루를 써서 사우스다코타 배드랜즈를 촬영하기로 했다. 이 지역은 웅장하고 독특한 지형으로 유명하다. 당신은 아마추어 사진가이고, 빛 조건에 매우 까다롭다.

배드랜즈에서 아름다운 장소를 찾았고, 주변 경관이 그림처럼 펼쳐져 있다. 이 장소에서 찍고 싶은 지형을 여러 개 골라 두었다. 각 지형마다 태양의 위치가 이상적인 가장 이른 시각과 가장 늦은 시각을 알고 있다. 다만 삼각대와 카메라 위치를 옮기는 데다 완벽을 추구하는 성격 탓에 사진 한 장을 찍는 데 시간이 꽤 걸린다. 이 지형들을 하루 안에 모두 찍을 수 있는지 알고 싶다.

입력

첫 줄에 두 정수 $n$ ( $1 \le n \le 10^5$ )과 $t$ ( $1 \le t \le 10^9$ )가 주어진다. $n$ 은 찍고 싶은 사진의 수이고, $t$ 는 사진 한 장을 찍는 데 걸리는 시간이다. 이어지는 $n$ 개의 줄에는 사진마다 작업할 수 있는 시간대가 주어진다. 각 줄에는 음이 아닌 정수 $a$ 와 $b$ 가 있으며, $a$ 는 그 사진 작업을 시작할 수 있는 가장 이른 시각, $b$ 는 그 사진을 끝내야 하는 시각이다. 단, $a + t \le b \le 10^{18}$ 이다.

출력

사진 $n$ 장을 모두 찍을 수 있으면 yes, 그렇지 않으면 no를 출력한다.

예제3

예제 1
입력
```
2 10
0 15
5 20
```
예상 출력
```
yes
```
예제 2
입력
```
2 10
1 15
0 20
```
예상 출력
```
no
```
예제 3
입력
```
2 10
5 30
10 20
```
예상 출력
```
yes
```