The Brick Stops Here

A factory manufactures brass bricks. Brass is an alloy of copper and zinc, and every brick weighs exactly $1000$ grams, of which the copper content may be anywhere from $1$ to $999$ grams. The factory produces $N$ different types of brick; each type has its own copper content and its own price, and all types are listed in a catalog.

A client wants to buy exactly $M$ bricks, and they must all be of different types. The chosen bricks are melted together, and the resulting mixture must contain at least $C_{min}$ and at most $C_{max}$ grams of copper per kilogram. Because every brick weighs one kilogram, melting $M$ bricks yields $M$ kilograms whose copper content is the sum of the chosen copper values; the requirement is therefore

$M \cdot C_{min} \le (\text{sum of the chosen copper contents}) \le M \cdot C_{max}.$

Among all selections that satisfy this requirement, the client wants the one with the smallest total price. For each client, determine that minimum total price. The values $M$, $C_{min}$, and $C_{max}$ differ from client to client.

The first line contains an integer $N$ ($1 \le N \le 200$), the number of brick types. Each of the next $N$ lines contains two integers: the copper content ($1$ to $999$ grams) and the price (in cents) of that brick type. No brick costs more than $1000$ cents.

The next line contains an integer $C$ ($1 \le C \le 100$), the number of clients. Each of the following $C$ lines contains three integers $M$, $C_{min}$, and $C_{max}$ ($1 \le M \le 20$, $1 \le C_{min} \le 999$, $1 \le C_{max} \le 999$), describing one client's request.

All input numbers are positive integers.

For each client, print on its own line the minimum possible total price (in cents) for a valid selection of $M$ distinct brick types. If no selection meets the client's requirements, print impossible for that client.