Большие планы

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

요약

겹치지 않는 체류 구간이 주어질 때, 연속한 b일 동안 체류 일수가 c일을 넘는지 판정한다.

난이도: 보통10점 중 6점
유형: 누적 합, 슬라이딩 윈도우, 정렬, 구간
정답자: 아직 제출이 없습니다

문제

Для путешествий по странам шенгенской зоны турист, который не является гражданином входящих в неё государств, должен получить шенгенскую визу. Она позволяет не только совершать путешествия в любую страну шенгенской зоны, но и свободно перемещаться между ними. Если же турист получает мультивизу --- он может совершать произвольное количество путешествий в страны шенгенской зоны, разумеется, если все поездки полностью укладываются в сроки действия визы.

Геннадий только что получил шенгенскую мультивизу на $a$ дней. Он уже запланировал $n$ поездок, когда узнал о наличии дополнительного требования миграционной полиции: для любых последовательных $b$ дней он может находиться в шенгенской зоне не более, чем $c$ дней. При этом день приезда и день отъезда считаются полностью проведёнными в шенгенской зоне днями. Теперь Геннадий просит вас определить, соответствует ли его план требованиям миграционной полиции, или ему лучше сразу отказаться от части поездок. % пока его не загребли

입력

Первая строка ввода содержит четыре целых числа $n$ , $a$ , $b$ и $c$ ( $1 \leq n \leq 100\\,000$ , $1 \leq c \leq b \leq a \leq 1\\,000\\,000$ ) --- количество поездок, запланированных Геннадием, продолжительность действия мультивизы в днях и параметры требования миграционной полиции соответственно.

Следующие $n$ строк описывают сами предполагаемые поездки. Каждое описание содержит два числа $l\_i$ и $r\_i$ ( $1 \leq l\_i \leq r\_i \leq a$ ) --- предполагаемые день отъезда и день приезда для $i$ -го путешествия соответственно.

Гарантируется, что поездки не перекрываются, то есть каждый из $a$ дней является частью не более чем одной поездки. Поездки перечислены в произвольном порядке, не обязательно в хронологическом.

출력

Выведите "Yes", если текущий план Геннадия не нарушает правил миграционной полиции по пребыванию на территории стран шенгенской зоны, в противном случае выведите "No" .

힌트

Во втором тесте из примера 180-дневное окно с дня $1$ по день $180$ (включительно) содержит $91$ день предполагаемого пребывания Геннадия в шенгенской зоне, а следовательно не попадает под правила миграционной полиции.

В третьем тесте из примера одним из 100-дневных окон, нарушающих правило, будет окно с дня $4$ по день $103$ (включительно). В этот период Геннадий планирует пробыть на территории стран шенгенской зоны с дня $4$ по день $21$ ( $18$ дней) и ещё с дня $100$ по день $103$ ( $4$ дня), что в сумме даст $22$ дня.

예제4

예제 1
입력
```
1 1000 180 90
2 91
```
예상 출력
```
Yes
```
예제 2
입력
```
1 1000 180 90
1 91
```
예상 출력
```
No
```
예제 3
입력
```
2 1000 100 20
3 21
100 110
```
예상 출력
```
No
```
예제 4
입력
```
2 300 10 10
181 270
1 90
```
예상 출력
```
Yes
```