This page is still under construction.

Parts of this page are still being built. What you see may change.

Racing Gems

Time limit2sMemory limit256 MB

Summary
Collect as many gems as possible while running upward with limited sideways speed from any start position.
Level

Medium7 of 10

Topics
Dynamic programming, Sorting, Binary search
Solved
No attempts yet

Problem

You are playing a racing game. Your character starts on the xx axis (y=0y = 0) and runs up the track, which is bounded by the line x=0x = 0 on one side and by the line x=wx = w on the other. You may start anywhere along the starting line, as long as the position is inside the track. The finish line is y=hy = h, and the game ends when you reach it.

Your vertical velocity is fixed at vv. Your horizontal velocity, on the other hand, can be any value between −v/r-v/r and v/rv/r, and you may change it at any time.

There is one gem at each of nn fixed points on the track. You want to collect as many gems as possible. How many gems can a single run collect?

Input

The first line contains four space separated integers nn, rr, ww, and hh (1≤n≤1051 \le n \le 10^5, 1≤r≤101 \le r \le 10, 1≤w,h≤1091 \le w, h \le 10^9).

Each of the next nn lines contains two space separated integers xix_i and yiy_i, the coordinates of the iith gem (0≤xi≤w0 \le x_i \le w, 0<yi≤h0 < y_i \le h). No two gems share a position.

The input does not contain a value for vv.

Output

Print, on a single line, the largest number of gems that can be collected during the race.

Examples3

  1. Example 1

    Input
    5 1 10 10
    8 8
    5 1
    4 6
    4 7
    7 9
    
    Expected output
    3
    
  2. Example 2

    Input
    5 1 100 100
    27 75
    79 77
    40 93
    62 41
    52 45
    
    Expected output
    3
    
  3. Example 3

    Input
    10 3 30 30
    14 9
    2 20
    3 23
    15 19
    13 5
    17 24
    6 16
    21 5
    14 10
    3 6
    
    Expected output
    4