막타 (스몰)

다이애나는 좋아하는 게임에서 골드를 최대한 많이 벌고 싶다. 다이애나는 자기 타워 옆에 서서 몬스터 $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 H_i \le 200$
• $0 \le G_i \le 10^6$
• $1 \le N \le 4$

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

예제의 두 번째 테스트 케이스에서 다이애나는 첫 번째 몬스터를 포기하고 타워에 넘긴다. 처음 두 차례는 세 번째 몬스터를 쏘아 체력을 80까지 깎아 두고, 그 덕분에 두 번째 몬스터와 세 번째 몬스터를 모두 자기 사격으로 마무리한다.