금화 모으기

고대 유적을 탐험하던 지민이는 금화가 가득한 방을 발견했다. 지민이가 금화를 줍는 동안에는 소리가 나서 몬스터들이 지민이에게 다가온다. 지민이가 금화 줍기를 멈추고 기다리면 소리가 사라지므로, 몬스터들은 같은 속도로 원래 위치를 향해 돌아간다. 이미 원래 위치에 있는 몬스터는 지민이가 기다리는 동안 움직이지 않는다.

지민이는 총 t(0 <= t <= 1,000,000) 단위 시간 동안 금화를 주울 수 있다. 한 단위 시간 동안에는 x(0 < x <= 10)개의 금화를 주울 수 있다. 각 몬스터는 지민이로부터 거리 d(0 < d <= 1,000,000)만큼 떨어져 있고, 한 단위 시간에 거리 s(0 < s <= 1,000,000)만큼 움직인다. 몬스터가 지민이에게 다가올 때와 원래 위치로 돌아갈 때의 속도는 같다.

모든 행동은 한 단위 시간마다 일어난다. 각 단위 시간마다 지민이는 금화를 줍거나 기다리는 행동 중 하나를 선택한다. 지민이가 금화를 주우면 몬스터들은 그 시간 동안 지민이에게 다가온다. 지민이가 기다리면 몬스터들은 그 시간 동안 원래 위치로 돌아가거나, 이미 원래 위치에 있다면 그 자리에 머문다. 몬스터가 지민이의 위치에 도착하는 순간 지민이가 금화 줍기를 멈추더라도 잡힌 것으로 본다.

금화와 주머니의 용량은 무한하다고 할 때, 지민이가 잡히지 않고 주울 수 있는 금화의 최대 개수를 구하라.

첫째 줄에 세 정수 t, x, m(0 <= m < 1,000)이 주어진다.

다음 m개의 줄에는 각 몬스터의 정보를 나타내는 두 정수 d, s가 주어진다.

지민이가 주울 수 있는 금화의 최대 개수를 출력한다.