페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5884
서브태스크

이벤트 순회 2초 1024MB

문제

정올 국가에는 두 개의 마을이 있으며 각각 1, 2로 번호가 매겨져 있습니다.

이 마을에서는 총 N개의 이벤트가 발생합니다. 이 이벤트에는 1에서 N까지 번호가 붙습니다.

이벤트 i (1 \le i \le N)는 마을 P_i에서 개최되며 개최 시간은 S_i+0.1부터 S_i+0.9까지 입니다. 여기서 S_i는 정수입니다.

이벤트 i에 참가하기 위해서는 시간 S_i+0.1부터 S_i+0.9까지 마을 P_i에 있어야 합니다.

정올이는 이벤트 순회를 하기로 했습니다. 이벤트 순회에서는 여러 이벤트에 참가하고 필요하다면 마을과 마을 사이를 이동할 수도 있습니다.

정올이는 시간 0부터 이벤트 순회를 시작합니다. 이 때 원하는 마을에서 시작할 수 있습니다.

정올이는 마을 1과 마을 2 사이를 왔다 갔다 이동할 수 있습니다. 두 마을 사이를 이동하는 데 걸리는 시간은 정올이가 이동을 시작할 때까지 참여한 이벤트의 수를 j라고 했을 때, D + K*j입니다.

이벤트와 마을 간의 이동에 관한 정보가 주어집니다. 당신은 정올이가 참가할 수 있는 최대 이벤트 수를 출력하는 프로그램을 작성해야 합니다.


입력

입력은 다음 형식으로 표준 입력에서 제공됩니다.

N \, D \, K

P_1 \, S_1

P_2 \, S_2

:

P_N \, S_N

[제한]

1 \le N \le 200,000
1 \le D \le 10^{12}

1 \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 \lt j \le N)

모든 입력 값은 정수입니다.


출력

표준 출력에 정올이 참가할 수 있는 최대 이벤트 수를 한 줄로 출력한다.


부분문제

번호 점수 조건
#18점

K=0, N \le 20

#211점

K=0, N \le 4\,000

#324점

K=0

#412점

N \le 160

#523점

N \le 4\,000

#622점

추가 제한 없음


예제1

입력
530
11
12
110
25
26
출력
4

다음과 같이 행동함으로써 정올이는 4개의 이벤트에 참가할 수 있다.

시간 0에서 정올이는 마을 1에 있습니다.

시간 1.1부터 시간 1.9까지 마을 1에서 이벤트 1에 참가한다.

시간 2.1부터 시간 2.9까지 마을 1에서 이벤트 2에 참가한다.

시간 3에서 시간 6까지 시간 3 (= D + K × 2)을 걸어 마을 1에서 마을 2로 이동한다.

시간 6.1부터 시간 6.9까지 마을 2에서 이벤트 5에 참가한다.

시간 7에서 시간 10까지 시간 3 (= D + K × 3)을 걸어 마을 2에서 마을 1로 이동한다.

시간 10.1부터 시간 10.9까지 마을 1에서 이벤트 3에 참가한다.

아무리 행동해도 5개 이상의 이벤트에 참가할 수 없기 때문에 4를 출력한다.

이 입력 예제는 모든 작은 문제의 제약 조건을 충족합니다.


예제2

입력
723
22
18
110
111
223
224
225
출력
6

예를 들어, 다음과 같이 행동함으로써 정올이는 6개의 이벤트에 참가할 수 있다.

시간 0에서 정올이는 마을 2에 있습니다.

시간 2.1부터 시간 2.9까지 마을 2에서 이벤트 1에 참가한다.

시간 3에서 시간 8까지 시간 5 (= D + K × 1)를 곱하여 마을 2에서 마을 1로 이동합니다.

시간 8.1부터 시간 8.9까지 마을 1에서 이벤트 2에 참가한다.

시간 11.1부터 시간 11.9까지 마을 1에서 이벤트 4에 참가한다.

시간 12에서 시간 23까지 시간 11 (= D + K × 3)을 걸어 마을 1에서 마을 2로 이동한다.

시간 23.1부터 시간 23.9까지 마을 2에서 이벤트 5에 참가한다.

시간 24.1부터 시간 24.9까지 마을 2에서 이벤트 6에 참가한다.

시간 25.1부터 시간 25.9까지 마을 2에서 이벤트 7에 참가한다.

아무리 행동해도 7개 이상의 이벤트에 참가할 수 없기 때문에 6을 출력한다.

이 입력 예는 작은 문제 4, 5, 6의 제약 조건을 충족합니다.


예제3

입력
121530
1155
2861
1646
1218
2450
256
1932
2295
2863
1612
238
2768
출력
8

예제4

입력
1589104
14379
1738
14862
14236
21416
19905
14775
24574
2439
13956
1955
28862
2801
22299
2575
출력
11

출처

JOI 2021 예선2

역링크