라스트 히트

다이애나는 즐겨 하는 게임에서 골드를 최대한 많이 벌고 싶어 한다. 다이애나는 자기 편 타워 가까이에 서 있고, 몬스터 $N$마리와 마주 보고 있다. 이 상황에서 다이애나와 타워가 번갈아 몬스터를 공격하며, 다이애나가 먼저 공격한다. 자기 차례에 다이애나는 살아 있는 몬스터 하나를 골라 공격할 수 있고, 아무것도 하지 않고 차례를 넘길 수도 있다. 타워는 자기 차례에 타워에서 가장 가까운 살아 있는 몬스터를 공격한다. 죽은 몬스터는 다이애나도 타워도 공격하지 않는다.

다이애나가 공격하면 그 몬스터의 체력이 $P$만큼 줄고, 타워가 공격하면 $Q$만큼 준다. 체력이 $1$ 미만으로 떨어진 몬스터는 죽는다. $i$번 몬스터의 처음 체력은 $H_i$이다. 다이애나의 공격이 $i$번 몬스터를 죽이면 다이애나가 골드 $G_i$를 받고, 타워의 공격이 죽이면 아무것도 받지 못한다. 다이애나가 얻을 수 있는 골드의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 $P$, $Q$, $N$이 공백으로 구분되어 주어진다. 이어지는 $N$개 줄 가운데 $i$번째 줄에는 $H_i$와 $G_i$가 공백으로 구분되어 주어진다.

몬스터는 타워에서 가까운 순서대로 주어진다. 즉, 타워는 번호가 $i$보다 작은 몬스터가 모두 죽은 뒤에야 $i$번 몬스터를 공격한다.

제한

• $1 \le T \le 100$
• $20 \le P \le 200$
• $20 \le Q \le 200$
• $1 \le N \le 100$
• $1 \le H_i \le 200$
• $0 \le G_i \le 10^6$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 다이애나가 얻을 수 있는 골드의 최댓값이다.

예제 가운데 $P = 20$, $Q = 60$인 테스트 케이스에서는 다이애나가 첫 번째 몬스터를 포기하는 편이 낫다. 처음 두 차례에 세 번째 몬스터를 공격해 체력을 $80$까지 떨어뜨려 두면, 두 번째 몬스터와 세 번째 몬스터의 마지막 타격을 모두 다이애나가 가져간다.