P13261 [GCJ 2014 #3] Last Hit

Diana needs your help maximizing her gold while playing her favorite game. She is often faced with a scenario where she is standing close to her tower and is facing $\mathbf{N}$ monsters. When that happens, Diana and the tower take turns shooting the monsters, and she goes first. During her turn, Diana may choose a monster to shoot at (this means Diana may choose to skip a turn). During its turn, the tower shoots the monster closest to it. Diana and the tower can not shoot dead monsters. If Diana shoots at a monster, its hit points are reduced by $\mathbf{P}$. If the tower shoots at a monster, its hit points are reduced by $\mathbf{Q}$. If a monster's hit points are reduced below 1, it is killed. The $i^{\text {th }}$ monster starts with $\mathbf{H}_{\mathrm{i}}$ hit points. Diana is awarded $\mathbf{G}_{\mathrm{i}}$ gold if her shot kills the $i^{\text {th }}$ monster, but none if the tower's shot kills it. What is the maximum amount of gold Diana can obtain?

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each case begins with one line containing three space-separated integers representing $\mathbf{P}, \mathbf{Q}$ and $\mathbf{N}$. $\mathbf{N}$ lines then follow, with the $i^{\text {th }}$ line containing two space-separated integers representing $\mathbf{H}_{\mathrm{i}}$ and $\mathbf{G}_{\mathrm{i}}$. The monsters are given in the order of their distance from the tower. In other words, the tower will shoot at the $i^{\text {th }}$ monster only if all monsters $

For each test case, output one line containing "Case #x: $y$", where x is the case number (starting from 1) and $y$ is the maximum amount of gold that Diana can obtain.

**Sample Explanation** In the second example, Diana should give up the first monster. During her first two turns she should soften up the third monster bringing it down to 80 hp, allowing her to easily get the last shot on the second and the third monsters. **Limits** - $1 \leq T \leq 100$ - $20 \leq \mathbf{P} \leq 200$ - $20 \leq \mathbf{Q} \leq 200$ - $1 \leq \mathbf{H}_{\mathrm{i}} \leq 200$ - $0 \leq \mathbf{G}_{\mathrm{i}} \leq 10^{6}$ **Small dataset(10 Pts)** - Time limit: ~~60~~ 3 seconds. - $1 \leq \mathbf{N} \leq 4$ **Large dataset(14 Pts)** - Time limit: ~~120~~ 5 seconds. - $1 \leq \mathbf{N} \leq 100$