Problem F. Ferryman of Hades

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  


"Ferryman of Hades" is a simple arcade game based on the Greek mythology. The main scene of the game is Styx river that is represented as a 1-dimensional line. Souls fall down from height H to this line. Charon must catch them in his boat when they touch the river line.

The boat of Charon is represented as a closed segment (containing its boundary points) of length L moving along line from the initial position [0, L].

Boat can move only from left to right with a fixed integer speed. It is known that i-th soul falls down to point Pi with a speed Vi.

A soul is caught if by the moment it crosses the river line, this point belongs to the boat.

Your program must, given H, L, Pi, and Vi, determine the minimum possible integer speed of the boat maximizing the number of caught souls.

Input format

Input contains integers H, L, and n, followed by n pairs of integers Pi, Vi.

Output format

Output must contain a single integer — the speed of the boat.


0 < (H, L, Vi) ≤ 106, 0 ≤ Pi ≤ 106,

1 ≤ n ≤ 2 ⋅ 105

Sample tests

No. Standard input Standard output
10 2 4
2 1
3 8
4 7
5 8
10 2 4
9 3
8 2
6 3
8 2

0.082s 0.012s 13