TLE '16 Contest 5 P3 - Flight Exam - DMOJ: Modern Online Judge

TLE '16 Contest 5 P3 - Flight Exam

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

ZQFMGB12

Problem type

Fax McClad cruising in Cronerian skies on his Kyuwing.

Fax McClad, Croneria's most well respected bounty hunter, needs to renew his flight license. In order to do so, he will have to take a flight examination.

For the examination, Fax is required to fly straight, but he can change his altitude. In front of him, there are $N$ ~N~ checkpoints: the $i^\text{th}$ ~i^\text{th}~ one is located $d_i$ ~d_i~ kilometers from his starting point and has an altitude of $a_i$ ~a_i~ meters.

Fax can increase his altitude at a rate of up to $I$ ~I~ meters per kilometer traveled and can decrease his altitude at a rate of up to $D$ ~D~ meters per kilometer traveled. Fax's initial altitude is $0$ ~0~ meters and he cannot go below this altitude.

Fax is able to do a special technique called the somersault. When he performs this technique, he will rise $S$ ~S~ meters before going back down to his original altitude in a loop fashion. In doing so, he can go through a checkpoint that is exactly $S$ ~S~ meters above him from his original altitude, if one exists.

Fax's exam ends when there are no more checkpoints in front of him. His score is determined by the number of checkpoints he passes. What is the maximum number of checkpoints that Fax can pass through?

Constraints

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~

$0 \le I, D, S, a_i \le 10^9$ ~0 \le I, D, S, a_i \le 10^9~

$1 \le d_i \le 10^9$ ~1 \le d_i \le 10^9~

For 40% of the points, $N \le 10$ ~N \le 10~.

Note to Python users: It is recommended to submit in PyPy.

Input Specification

The first line of input will contain four space-separated integers: $N$ ~N~, $I$ ~I~, $D$ ~D~, and $S$ ~S~.

$N$ ~N~ lines of input follow. The $i^\text{th}$ ~i^\text{th}~ line will contain two space-separated integers: $d_i$ ~d_i~ and $a_i$ ~a_i~, specifying the distance and the altitude of the $i^\text{th}$ ~i^\text{th}~ checkpoint. It is guaranteed that all $(d_i,a_i)$ ~(d_i,a_i)~ are pairwise distinct.

Output Specification

Output a single integer, the maximum number of checkpoints that Fax can pass through.

Sample Input

6 400 200 300
2 600
3 1000
3 1200
3 1300
5 700
6 200

Sample Output

Diagram for Sample

$\text{[math]}$

The black points signify the checkpoints, and the red line is the optimal path that Fax McClad can take.

Comments

0

jimgao commented on Jan. 20, 2017, 3:08 p.m.

Can he perform the somersault when he is not currently at a checkpoint?

0

r3mark commented on Jan. 20, 2017, 3:16 p.m.

Yes.