2223번 - 금화

고대 유적을 탐험하던 지민이는 금화가 가득 들어 있는 방을 발견하였다. 지민이는 가져간 주머니에 가득 금화를 담으려고 하였는데, 금화를 주머니에 담을 때 나는 소리 때문에 고대 유적 안의 몬스터들이 움직이게 된다는 사실을 알게 되었다. 다행히도 이 몬스터들은 지능적이지 않아서, 금화를 주워 담는 것을 멈추고 기다리면, 금화가 짤랑거리는 소리가 나지 않기 때문에 다시 원래의 자리로 돌아가고, 다시 소리가 나면 다가오는 식으로 움직인다. 몬스터에게 잡히지 않기 위해서 지민이는 금화를 적당히 주워 담다가 적당히 기다리는 것을 반복하기로 하였다.

지민이는 총 t(0 ≤ t ≤ 1,000,000) 단위의 시간 동안 금화를 주워 담을 수 있다. 또한 한 단위의 시간 동안 x(0 < x ≤ 10)개의 금화를 주워 담을 수 있다. 각각의 몬스터들은 지민이로부터 d(0 < d ≤ 1,000,000)만큼의 거리에 위치해 있으며, 단위 시간동안 s(0 < s ≤ 1,000,000)만큼의 거리를 움직인다. 몬스터가 지민이에게 다가올 때와 원래의 위치로 돌아갈 때 모두 같은 속도로 움직인다.

문제를 간명하게 만들기 위해서 모든 행동은 단위 시간마다 일어난다고 가정하자. 즉 지민이는 1만큼의 시간동안 금화를 줍거나 멈추는 행위 중에서 하나를 선택해야 한다. 몬스터들도 1만큼의 시간동안 다가오거나(지민이가 그 시간에 금화를 줍는 경우), 원래의 위치로 돌아가거나(지민이가 그 시간에 멈춰 있는 경우), 아니면 원래의 위치에서 가만히 있게 된다(지민이가 그 시간에 멈춰 있으며 몬스터가 원래의 위치에 있는 경우). 만약 몬스터가 지민이의 위치에 도착하는 순간 금화를 줍는 행위를 멈추게 되면, 이 역시 몬스터에게 잡히는 것으로 간주한다.

이러한 정보가 주어졌을 때, 지민이가 주워 담을 수 있는 금화의 최대 개수를 구하는 프로그램을 작성하시오. 금화는 무한히 많으며, 금화를 주워 담을 주머니 역시 무한히 크다고 가정한다.

첫째 줄에 세 정수 t, x, m(0 ≤ m < 1,000)이 주어진다. 다음 m개의 줄에는 각 몬스터에 대한 정보를 나타내는 두 정수 d, s가 주어진다.

첫째 줄에 답을 출력한다.