이벤트 순회

문제

IOI 국에는 $2$ 개의 마을이 있으며, 각각 $1, 2$ 라는 번호가 붙어 있다.

이 마을들에서는 합계 $N$ 개의 이벤트가 열린다. 이 이벤트들에는 $1$ 부터 $N$ 까지의 번호가 붙어 있다. 이벤트 $i$ ($1 \le i \le N$) 는 마을 $P_{i}$ 에서 개최되며, 개최 시각은 시각 $S_{i} + 0.1$ 부터 시각 $S_{i} + 0.9$ 까지이다. 여기서 $S_{i}$ 는 정수이다. JOI 군이 이벤트 $i$ 에 참가하기 위해서는 시각 $S_{i} + 0.1$ 부터 시각 $S_{i} + 0.9$ 까지 계속 마을 $P_{i}$ 에 있어야 한다.

JOI 군은 이벤트 순회를 하기로 했다. 이벤트 순회에서는 몇 개의 이벤트에 참가하며, 필요하다면 마을과 마을 사이를 이동할 수도 있다. JOI 군은 시각 $0$ 부터 이벤트 순회를 시작한다. 이때 원하는 마을에서 시작할 수 있다.

JOI 군은 마을 $1$ 과 마을 $2$ 사이를 양방향으로 이동할 수 있다. $2$ 개의 마을 사이를 이동하는 데 걸리는 시간은, JOI 군이 그 이동을 시작하는 시각까지 참가한 이벤트의 수를 $j$ 라고 할 때 $D + K \times j$ 이다.

이벤트와 마을 사이의 이동에 관한 정보가 주어지므로, JOI 군이 참가할 수 있는 이벤트 수의 최댓값을 구하는 프로그램을 작성하시오.

제한

• $1 \le N \le 200\,000$.
• $1 \le D \le 10^{12}$.
• $0 \le K \le 10^{12}$.
• $1 \le P_{i} \le 2$ ($1 \le i \le N$).
• $1 \le S_{i} \le 10^{12}$ ($1 \le i \le N$).
• $S_{i} \neq S_{j}$ ($1 \le i < j \le N$).
• 입력되는 값은 모두 정수이다.

서브태스크

1. ($8$ 점) $K = 0$, $N \le 20$.
2. ($11$ 점) $K = 0$, $N \le 4\,000$.
3. ($24$ 점) $K = 0$.
4. ($12$ 점) $N \le 160$.
5. ($23$ 점) $N \le 4\,000$.
6. ($22$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$N$ $D$ $K$
$P_{1}$ $S_{1}$
$P_{2}$ $S_{2}$
$:$
$P_{N}$ $S_{N}$

출력

표준 출력에 JOI 군이 참가할 수 있는 이벤트 수의 최댓값을 $1$ 줄로 출력한다.

예제 입력 1

5 3 0
1 1
1 2
1 10
2 5
2 6

예제 출력 1

4

예를 들어 다음과 같이 행동함으로써 JOI 군은 $4$ 개의 이벤트에 참가할 수 있다.

1. 시각 $0$ 에 JOI 군은 마을 $1$ 에 있다.
2. 시각 $1.1$ 부터 시각 $1.9$ 까지 마을 $1$ 에서 이벤트 $1$ 에 참가한다.
3. 시각 $2.1$ 부터 시각 $2.9$ 까지 마을 $1$ 에서 이벤트 $2$ 에 참가한다.
4. 시각 $3$ 부터 시각 $6$ 까지 시간 $3$ ($= D + K \times 2$) 을 들여 마을 $1$ 에서 마을 $2$ 로 이동한다.
5. 시각 $6.1$ 부터 시각 $6.9$ 까지 마을 $2$ 에서 이벤트 $5$ 에 참가한다.
6. 시각 $7$ 부터 시각 $10$ 까지 시간 $3$ ($= D + K \times 3$) 을 들여 마을 $2$ 에서 마을 $1$ 로 이동한다.
7. 시각 $10.1$ 부터 시각 $10.9$ 까지 마을 $1$ 에서 이벤트 $3$ 에 참가한다.

어떻게 행동하더라도 $5$ 개 이상의 이벤트에 참가할 수는 없으므로 $4$ 를 출력한다.

이 예제는 모든 서브태스크의 제약을 만족한다.

예제 입력 2

7 2 3
2 2
1 8
1 10
1 11
2 23
2 24
2 25

예제 출력 2

6

예를 들어 다음과 같이 행동함으로써 JOI 군은 $6$ 개의 이벤트에 참가할 수 있다.

1. 시각 $0$ 에 JOI 군은 마을 $2$ 에 있다.
2. 시각 $2.1$ 부터 시각 $2.9$ 까지 마을 $2$ 에서 이벤트 $1$ 에 참가한다.
3. 시각 $3$ 부터 시각 $8$ 까지 시간 $5$ ($= D + K \times 1$) 를 들여 마을 $2$ 에서 마을 $1$ 로 이동한다.
4. 시각 $8.1$ 부터 시각 $8.9$ 까지 마을 $1$ 에서 이벤트 $2$ 에 참가한다.
5. 시각 $11.1$ 부터 시각 $11.9$ 까지 마을 $1$ 에서 이벤트 $4$ 에 참가한다.
6. 시각 $12$ 부터 시각 $23$ 까지 시간 $11$ ($= D + K \times 3$) 을 들여 마을 $1$ 에서 마을 $2$ 로 이동한다.
7. 시각 $23.1$ 부터 시각 $23.9$ 까지 마을 $2$ 에서 이벤트 $5$ 에 참가한다.
8. 시각 $24.1$ 부터 시각 $24.9$ 까지 마을 $2$ 에서 이벤트 $6$ 에 참가한다.
9. 시각 $25.1$ 부터 시각 $25.9$ 까지 마을 $2$ 에서 이벤트 $7$ 에 참가한다.

어떻게 행동하더라도 $7$ 개 이상의 이벤트에 참가할 수는 없으므로 $6$ 을 출력한다.

이 예제는 서브태스크 $4, 5, 6$ 의 제약을 만족한다.

예제 입력 3

12 153 0
1 155
2 861
1 646
1 218
2 450
2 56
1 932
2 295
2 863
1 612
2 38
2 768

예제 출력 3

8

이 예제는 모든 서브태스크의 제약을 만족한다.

예제 입력 4

15 89 104
1 4379
1 738
1 4862
1 4236
2 1416
1 9905
1 4775
2 4574
2 439
1 3956
1 955
2 8862
2 801
2 2299
2 575

예제 출력 4

11

이 예제는 서브태스크 $4, 5, 6$ 의 제약을 만족한다.