Last Hit

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

A shot from Diana lowers the monster's hit points by $P$, and a shot from the tower lowers them by $Q$. A monster whose hit points drop below $1$ dies. Monster $i$ starts with $H_i$ hit points. If Diana's shot kills monster $i$, she receives $G_i$ gold. If the tower's shot kills it, she receives nothing. Find the largest amount of gold Diana can obtain.

The first line contains the number of test cases $T$. The first line of each test case contains $P$, $Q$ and $N$, separated by spaces. The $i$-th of the next $N$ lines contains $H_i$ and $G_i$, separated by a space.

The monsters are listed in order of their distance from the tower. The tower shoots monster $i$ only after every monster with a smaller number is dead.

Limits

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

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

In the sample test case with $P = 20$ and $Q = 60$, Diana should give up the first monster. If she spends her first two turns on the third monster and brings it down to $80$ hit points, she takes the last hit on both the second and the third monster.