Last Hit (Small)

Diana is playing her favorite game and wants to earn as much gold as she can. She stands next to her own tower, facing $N$ monsters. Diana and the tower take turns shooting the monsters, and Diana shoots first. On her turn Diana may pick one living monster and shoot it, or she may do nothing and pass. On its turn the tower shoots the living monster closest to it. Neither Diana nor the tower can shoot a monster that is already dead.

A shot from Diana lowers the target's hit points by $P$, and a shot from the tower lowers them by $Q$. A monster whose hit points drop below 1 is dead. The $i$-th monster starts with $H_i$ hit points. If the shot that kills the $i$-th monster is Diana's, she receives $G_i$ gold; if it is the tower's, she receives nothing. Find the maximum amount of gold Diana can obtain.

The first line contains the number of test cases $T$. The first line of each test case contains three space-separated integers $P$, $Q$ and $N$. Then $N$ lines follow, and the $i$-th of them contains two space-separated integers $H_i$ and $G_i$.

The monsters are given in order of their distance from the tower, nearest first. The tower shoots the $i$-th monster only after every monster before it is dead.

Constraints

• $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$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the maximum amount of gold Diana can obtain.

In the second test case of the sample, Diana gives up the first monster and leaves it to the tower. She spends her first two turns on the third monster, cutting it down to 80 hit points, and that lets her land the killing shot on both the second and the third monster.