Description

There is a huge mountain outside Kicc's house, and Kicc has to climb the mountain every time he wants to go out. It costs him a lot of time and he wants to change the situation. Yes, he figures out a good idea - to move the mountain away! But there is a problem. There are some wild animals not too far away from the mountain. Kicc will make noises when digging or moving the stones. If the animals hear the sound made by Kicc, they will come closer. If an animal reaches the mountain and sees Kicc, the animal will eat Kicc immediately. But the animals are stupid - when they do not hear the sound, they will go back along the exact route they come to the mountain until they are in the place where they start. When they hear the sound again, they will come to the mountain again no matter where they are. In this situation, Kicc has to stop sometimes before the first animal arrives to avoid being eaten. You should notice that as soon as the animal arrive in the mountain, Kicc will be eaten, no matter he stops his work or not.

Kicc has t units of time per day and he can handle x units of stones in one unit of time (This action will make noises). There are m animals near the mountain. The i-th animal stays away the mountain with d_i units of distance and can run s_i units of distance in one of unit time. Kicc wants to know the most amount of stones he can handle every day (You can assume the amount of the stones in the mountain is infinite). To make it easier, you may assume that Kicc can work or rest for only integer units of time, for example, 1 unit of time, or 2 units of time, or 3 units of time, and so on.

Input

The first line contains an integer t (0 <= t < 1000000), and an integer x (0 < x < 10). The second line contains a single integer m (0 <= m < 1000). There are m lines following the second line, each has 2 integers d_i (0 < d_i < 1000000) and s_i (0 < s_i < 1000000).

Output

The output should contain a single integer which means the most amount of stones Kicc can move away in one day.

100 5
2
1000 5
100 1

495

Source

Beijing 2005 Preliminary