품질 좋은 음식

고향을 떠나 대도시로 이사했다. 새 환경은 다 마음에 드는데 음식만은 아니다. 고향 식당이 내던 음식(아래에서는 품질 좋은 음식이라고 부른다)이 계속 생각난다.

다행히 고향에서 가장 큰 식당이 배달을 한다. 한 번 배달할 때 음식을 원하는 만큼 살 수 있다. 배달 한 번마다 배달비가 붙고, 그 금액은 그 배달에서 음식을 얼마나 샀는지와 상관없이 항상 같다.

이 식당은 여러 종류의 음식을 판다. 각 종류에는 한 끼당 가격과 상하기까지의 기간이 있다. 한 끼는 하루치 식사이고, 한 번 먹은 끼니는 다시 먹을 수 없다. 상하기까지의 기간이 $t$인 음식은 받은 날을 0일째로 셀 때 $t$일째까지 먹을 수 있다. $t$가 0이면 배달받은 날에 먹어야 한다.

한 번 배달에 돈이 허락하는 만큼 여러 종류를 섞어 살 수 있고, 각 종류를 몇 끼든 살 수 있다. 상하기까지의 기간이 $t$인 음식을 한 번 배달에 $t + 1$끼보다 많이 시키면 적어도 한 끼는 먹기 전에 상한다.

배달은 아주 빨라서 주문한 날에 음식을 모두 받고, 그날 바로 먹어도 된다. 품질 좋은 음식을 얻는 방법은 배달뿐이다.

가진 돈을 끼니 값과 배달비에 쓴다고 할 때, 1일째부터 하루도 거르지 않고 품질 좋은 음식을 먹을 수 있는 최대 일수를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $M$, $F$, $N$이 주어지고, 각각 가진 돈, 배달비, 식당이 파는 음식 종류의 수이다. 이어서 $N$개의 줄이 주어지며, $i$번째 줄에는 두 정수 $P_i$와 $S_i$가 주어진다. 각각 그 종류의 한 끼당 가격과 상하기까지의 기간이다.

제한

• $1 \le T \le 50$
• $1 \le F \le M$
• $1 \le N \le 200$
• $1 \le P_i \le M$
• $0 \le S_i \le 2\,000\,000$
• $1 \le M \le 2\,000\,000$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 매일 품질 좋은 음식을 한 끼 이상 먹을 수 있는 최대 일수이다.

첫 번째 예제의 첫 케이스는 이렇게 3일을 채운다. 도시에서 보내는 첫날에 첫 번째 종류 한 끼와 두 번째 종류 한 끼를 사고(배달비까지 합쳐 20을 쓴다), 그날 첫 번째 종류를 먹은 뒤 다음 날 두 번째 종류를 먹는다. 셋째 날에 첫 번째 종류 한 끼를 다시 사서 그날 먹는다.