Gold Coin Collection

While exploring an ancient ruin, Jimin finds a room full of gold coins. Whenever Jimin collects coins, the sound makes the monsters move toward him. If Jimin stops collecting and waits, the sound disappears, so the monsters move back toward their original positions at the same speed. A monster that is already at its original position stays there while Jimin waits.

Jimin can spend a total of t (0 <= t <= 1,000,000) time units collecting coins. In one time unit, he can collect x (0 < x <= 10) coins. Each monster is initially at distance d (0 < d <= 1,000,000) from Jimin and moves distance s (0 < s <= 1,000,000) in one time unit. A monster uses the same speed when approaching Jimin and when returning to its original position.

All actions happen in whole time units. During each time unit, Jimin must choose either to collect coins or to wait. If he collects coins, the monsters move toward him during that time unit. If he waits, the monsters move back toward their original positions during that time unit, or stay still if they are already there. If a monster reaches Jimin exactly when he stops collecting, Jimin is still considered caught.

Assuming there are infinitely many coins and the bag has unlimited capacity, compute the maximum number of coins Jimin can collect without being caught.

The first line contains three integers t, x, and m (0 <= m < 1,000).

Each of the next m lines contains two integers d and s, describing one monster.

Print the maximum number of coins Jimin can collect.