Floodgates

A dam has $n$ floodgates. Each floodgate has its own flow rate and channel, and opening it can cause flood damage to the downstream area.

Opening floodgate $G_i$ drains $F_i$ m³ of water per hour and incurs a damage cost of $C_i$. This damage cost is a fixed cost that occurs whenever the gate is opened at all, regardless of how long it stays open.

The dam holds $V$ m³ of water, and all of it must be drained within $T$ hours. Write a program that finds how to open the floodgates so that the total damage cost is minimized.

Each floodgate operates independently, opening time is measured in whole hours, and a gate can be kept open for at most $T$ hours. Therefore, opening gate $G_i$ can drain at most $F_i \times T$ m³ of water.

For example, suppose there are 4 floodgates whose flow rates and damage costs are as follows.

To drain 5000000 m³ within 7 hours, opening only $G_1$ drains $720000 \times 7 = 5040000$ m³, which is enough, at a cost of 120000.

To drain 5000000 m³ within 30 hours, opening $G_2$ and $G_3$ together drains 180000 m³ per hour, which is more than enough within 30 hours, at a cost of $60000 + 50000 = 110000$.

The first line contains the number of floodgates $n$. ($1 \le n \le 20$)

Each of the next $n$ lines contains the flow rate $F_i$ (m³/hour) and the damage cost $C_i$ of gate $G_i$, separated by a space.

The next line contains the number of queries $m$. ($1 \le m \le 50$)

Each of the following $m$ lines contains $V$ and $T$ for one query, meaning that the stored $V$ m³ of water must all be drained within $T$ hours.

($1 \le F_i, C_i, V \le 10^9$, $1 \le T \le 1000$)

For each query, print one line in the format Case k: X, where $k$ is the query number starting from 1 and $X$ is the minimum damage cost. If the $V$ m³ of water cannot be drained within $T$ hours, print IMPOSSIBLE instead of $X$.