만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

이벤트 순회

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

요약
두 도시에서 열리는 N개의 행사마다 시간이 정해져 있고, 도시를 옮길 때 D에 K와 지금까지 참석한 행사 수를 곱한 값을 더한 시간이 걸릴 때, 참석할 수 있는 행사의 최대 개수를 구합니다.
난이도

어려움10점 중 8점

유형
동적 계획법, 정렬, 세그먼트 트리
정답자
아직 제출이 없습니다

문제

IOI 나라에는 마을이 2개 있으며, 각각 11, 22번 번호가 붙어 있다.

이 마을들에서는 총 NN개의 이벤트가 열린다. 이벤트에는 11부터 NN까지 번호가 붙어 있다. 이벤트 ii (1≤i≤N1 \leq i \leq N)는 마을 PiP_i에서 열리며, 개최 시각은 Si+0.1S_i + 0.1부터 Si+0.9S_i + 0.9까지이다. 여기서 SiS_i는 정수이다. JOI 군이 이벤트 ii에 참가하려면 시각 Si+0.1S_i + 0.1부터 Si+0.9S_i + 0.9까지 계속 마을 PiP_i에 있어야 한다.

JOI 군은 이벤트 순회를 하기로 했다. 이 순회에서는 여러 이벤트에 참가할 수 있고, 필요하면 마을 사이를 이동할 수도 있다. JOI 군은 시각 00에 순회를 시작하며, 어느 마을에서 시작해도 된다.

JOI 군은 마을 11과 마을 22 사이를 양방향으로 이동할 수 있다. 두 마을 사이를 이동하는 데는, 이동을 시작하는 시각까지 참가한 이벤트 수를 jj라고 할 때 D+K×jD + K \times j의 시간이 걸린다.

이벤트와 각 이벤트가 열리는 마을이 주어질 때, JOI 군이 참가할 수 있는 이벤트 수의 최댓값을 구하라.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.

N D K
P1 S1
P2 S2
:
PN SN

출력

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

제한

  • 1≤N≤2000001 \leq N \leq 200000.
  • 1≤D≤10121 \leq D \leq 10^{12}.
  • 0≤K≤10120 \leq K \leq 10^{12}.
  • 1≤Pi≤21 \leq P_i \leq 2 (1≤i≤N1 \leq i \leq N).
  • 1≤Si≤10121 \leq S_i \leq 10^{12} (1≤i≤N1 \leq i \leq N).
  • Si≠SjS_i \neq S_j (1≤i<j≤N1 \leq i < j \leq N).
  • 입력되는 값은 모두 정수이다.

예제4

  1. 예제 1

    입력
    5 3 0
1 1
1 2
1 10
2 5
2 6
    예상 출력
    4

  2. 예제 2

    입력
    7 2 3
2 2
1 8
1 10
1 11
2 23
2 24
2 25
    예상 출력
    6

  3. 예제 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
    예상 출력
    8

  4. 예제 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
    예상 출력
    11