Problem Description

In the country of IOI, there are 2 towns, numbered 1 and 2.

A total of $ N $ events will be held in these towns. These events are numbered from 1 to $ N $. Event $ i $ ($1 \leq i \leq N$) will be held in town $ P_i $ from time $ S_i + 0.1 $ to time $ S_i + 0.9 $. Here, $ S_i $ is an integer. To participate in event $ i $, JOI must be in town $ P_i $ from time $ S_i + 0.1 $ to time $ S_i + 0.9 $.

JOI has decided to go event hopping. In event hopping, he will participate in some events and may also move between towns if necessary. JOI starts event hopping at time 0, and he can start in any town.

JOI can move bidirectionally between towns 1 and 2. The time it takes to move between the two towns is $D + K \times j$, where $ j $ is the number of events JOI has participated in up to the time he starts the move.

Given the information about the events and the movement between towns, create a program to find the maximum number of events JOI can participate in.

Input Format

The input is given from the standard input in the following format:

$ N $ $ D $ $ K $ $ P_1 $ $ S_1 $ $ P_2 $ $ S_2 $ $\vdots$ $ P_N $ $ S_N $

Output Format

Output the maximum number of events JOI can participate in to the standard output on a single line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4

Sample Input #2

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

Sample Output #2

6

Sample Input #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

Sample Output #3

8

Sample Input #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

Sample Output #4

11

Notes/Hints

Constraints

• $1 \leq N \leq 200,000$.
• $1 \leq D \leq 10^{12}$.
• $0 \leq K \leq 10^{12}$.
• $1 \leq P_i \leq 2$ ($1 \leq i \leq N$).
• $1 \leq S_i \leq 10^{12}$ ($1 \leq i \leq N$).
• $S_i \neq S_j$ ($1 \leq i < j \leq N$).
• All values given in the input are integers.

Subtasks

1. ($ 8 $ points) $ K = 0 $, $N \leq 20$.
2. ($ 11 $ points) $ K = 0 $, $N \leq 4,000$.
3. ($ 24 $ points) $ K = 0 $.
4. ($ 12 $ points) $N \leq 160$.
5. ($ 23 $ points) $N \leq 4,000$.
6. ($ 22 $ points) No additional constraints.

Sample Explanation 1

For example, JOI can participate in 4 events by doing the following:
1. At time 0, JOI is in town 1.
2. Participates in event 1 in town 1 from time 1.1 to 1.9.
3. Participates in event 2 in town 1 from time 2.1 to 2.9.
4. Moves from town 1 to town 2 from time 3 to 6 (time = $D + K \times 2$).
5. Participates in event 5 in town 2 from time 6.1 to 6.9.
6. Moves from town 2 to town 1 from time 7 to 10 (time = $D + K \times 3$).
7. Participates in event 3 in town 1 from time 10.1 to 10.9.
It is impossible to participate in more than 5 events, so output 4. This input example satisfies the constraints of all subtasks.

Sample Explanation 2

For example, JOI can participate in 6 events by doing the following:
1. At time 0, JOI is in town 2.
2. Participates in event 1 in town 2 from time 2.1 to 2.9.
3. Moves from town 2 to town 1 from time 3 to 8 (time = $D + K \times 1$).
4. Participates in event 2 in town 1 from time 8.1 to 8.9.
5. Participates in event 4 in town 1 from time 11.1 to 11.9.
6. Moves from town 1 to town 2 from time 12 to 23 (time = $D + K \times 3$).
7. Participates in event 5 in town 2 from time 23.1 to 23.9.
8. Participates in event 6 in town 2 from time 24.1 to 24.9.
9. Participates in event 7 in town 2 from time 25.1 to 25.9.
It is impossible to participate in more than 7 events, so output 6. This input example satisfies the constraints of subtasks 4, 5, and 6.

Sample Explanation 3

This input example satisfies the constraints of all subtasks.

Sample Explanation 4

This input example satisfies the constraints of subtasks 4, 5, and 6.

见题面 Input 部分

见题面 Output 部分