favorite We need a little bit of your help to keep things running, click on this banner to learn more

Racing Gems

Racing Gems

You are playing a racing game. Your character starts at the x axis (y = 0) and proceeds up the race track, which has a boundary at the line x = 0 and another at x = w. You may start the race at any horizontal position you want, as long as it is within the track boundary. The finish line is at y = h, and the game ends when you reach that line. You proceed at a fixed vertical velocity v, but you can control your horizontal velocity to be any value between -v / r and v / r, and change it at any time.

There are n gems at speci fic points on the race track. Your job is to collect as many gems as possible. How many gems can you collect?


The first line contains four space-separated integers n, r, w and h (1n105, 1r10, 1w, h109). Each of the following n lines contains two space-separated integers xi and yi, denoting the coordinate of the i-th gem (0xiw, 0 < yih). There will be at most one gem per location.

The input does not include a value for v.


Print the maximum number of gems that can be collected during the race.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 1 10 10
8 8
5 1
4 6
4 7
7 9
Output example #1
Input example #2
5 1 100 100
27 75
79 77
40 93
62 41
52 45
Output example #2
Source 2015 ACM North America - Pacific Northwest, Division 1, Problem G