고급 음식

당신은 방금 고향을 떠나 대도시로 이사했다! 음식만 빼면 새로운 환경의 모든 것이 마음에 든다. 당신의 고향에서는 그 지역에서 가장 훌륭한 음식인 "고급 음식"을 제공하며, 당신은 분명 그 음식이 그리울 것이다.

다행히 고향에서 가장 큰 식당은 음식 배달 서비스를 제공한다. 한 번의 배달로 원하는 만큼의 음식을 구매할 수 있다. 한 번의 배달에서 구매하는 음식의 양과 관계없이 배달할 때마다 일정한 배달료가 부과된다.

이 식당은 여러 종류의 음식을 판매한다. 각 음식 종류에는 두 가지 속성, 즉 한 끼당 가격과 상하기까지 걸리는 시간이 있다. 음식 한 "끼"는 당신이 하루 동안 먹을 양이며, 한 끼를 먹고 나면 다시 먹을 수 없다. 음식 종류의 상하기까지 걸리는 시간은 음식을 받은 날부터 세어 그 음식을 여전히 먹을 수 있는 최대 일수이다. 상하기까지 걸리는 시간이 영이라는 것은 배달받은 당일에 그 종류의 음식을 먹어야 한다는 뜻이다.

한 번의 배달로 가진 돈이 허용하는 한 서로 다른 음식 종류를 원하는 만큼 구매할 수 있고, 각 종류의 음식도 원하는 만큼의 끼니를 구매할 수 있다. 특정 음식 종류의 상하기까지 걸리는 시간이 t이라면, 한 번의 배달로 그 음식을 t+1끼보다 많이 주문하는 것은 의미가 없다는 점에 유의한다. 먹기 전에 적어도 한 끼가 상하게 되기 때문이다.

이 식당의 배달 서비스는 매우 빠르므로 구매한 당일에 한 번의 배달에 포함된 모든 음식을 받으며, 같은 날 그중 일부를 먹을 수도 있다. 고급 음식을 받을 수 있는 유일한 방법은 음식 배달이다.

식사 가격과 배달료에 사용할 수 있는 일정한 금액이 주어질 때, 매일 고급 음식을 먹을 수 있는 최대 일수는 얼마인가?

제한

메모리 제한: 1GB. 시간 제한: 테스트 세트당 20초. 1 ≤ T ≤ 50. 1 ≤ F ≤ M. 1 ≤ N ≤ 200. 1 ≤ $P_{i}$ ≤ M.

테스트 세트 1 (공개 판정)

0 ≤ $S_{i}$ ≤ 2,000,000. 1 ≤ M ≤ 2,000,000.

테스트 세트 2 (비공개 판정)

0 ≤ $S_{i}$ ≤ $10^{18}$. 1 ≤ M ≤ $10^{18}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 M, F, N으로 시작하며, 각각 가진 돈의 액수, 배달료, 식당에서 제공하는 음식 종류의 수를 나타낸다. 이어지는 N개의 줄에는 각각 두 정수 $P_{i}$와 $S_{i}$가 주어지며, 각각 한 음식 종류의 한 끼당 가격과 상하기까지 걸리는 시간을 나타낸다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 매일 적어도 한 끼의 고급 음식을 계속 먹을 수 있는 최대 일수이다.

첫 번째 테스트 케이스의 예시 상황은 도시에 온 첫날 첫 번째 종류의 음식 한 끼와 두 번째 종류의 음식 한 끼를 구매하는 것이다. 이때 총비용은 20이다. 그날 첫 번째 종류의 음식을 먹고, 다음 날 두 번째 종류의 음식을 먹는다. 셋째 날에는 첫 번째 종류의 음식 한 끼를 구매하여 같은 날 먹는다. 이렇게 사흘 동안 먹을 수 있다.