Задачи
Water Gate Management
Water Gate Management
A dam has \textbf{n} water gates to let out water when necessary. Each water gate has its own capacity, water path and affected areas in the downstream. The affected areas may have a risk of flood when the water gate is open. The cost of potential damage caused by a water gate is measured in number calculated from the number of people and areas estimated to get affected.
Suppose a water gate \textbf{G_i} has the volumetric flow rate of \textbf{F_i} m^3/hour and the damage cost of \textbf{C_i}. In a certain situation, the dam has the volume \textbf{V} m^\{3 \}of water to flush out within \textbf{T} hours. Your task is to manage the opening of the water gates in order to get rid of \textit{at least} the specified volume of water within a limited time in condition that the damage cost is minimized.
For example, a dam has \textbf{4} water gates and their properties are shown in the following table.
\textit{Case 1:} You have to flush out the water \textbf{5} million m^\{3 \}within \textbf{7} hours. The minimum cost will be \textbf{120,000} by letting the water gate \textbf{G_1} open for \textbf{7} hours.
\textit{Case 2:} You have to flush out the water \textbf{5} million m^\{3 \}within \textbf{30} hours. The minimum cost will be \textbf{110,000} by letting the water gates \textbf{G_2} and \textbf{G_3} open, for example, \textbf{G_2} is open for \textbf{29} hours and \textbf{G_3} is open for \textbf{28} hours.
Note that each water gate is independent and it can be open only in a unit of whole hour (no fraction of hour).
\InputFile
The first line includes an integer \textbf{n} indicating number of water gates (\textbf{1} ≤ \textbf{n}\textit{ }≤ \textbf{20}). Then the next \textbf{n} lines contain, in each line, two integers: \textbf{F_i} and \textbf{C_i} corresponding to the flow rate (m^3/hour) and the damage cost of the water gate \textbf{G_i}_\{ \}respectively. The next line contains the number \textbf{m} which is the number of test cases (\textbf{1} ≤ \textbf{m}\textit{ }≤ \textbf{50}). The following \textbf{m}lines contain, in each line, two integers: \textbf{V} and \textbf{T} corresponding to the volume (m^3) of water to let out within \textbf{T} hours.
\textbf{1} ≤ \textbf{F_i}, \textbf{V}\textit{, }\textbf{C_i} ≤ \textbf{10}^9, \textbf{1} ≤ \textbf{T} ≤ \textbf{1000}
\OutputFile
For each test case, print out the minimum cost in the exact format shown in the sample output below. If it is \textbf{not}possible to let out the water of volume \textbf{V} in \textbf{T} hours from the dam, print out "\textbf{IMPOSSIBLE}" (without quotation marks).
Входные данные #1
4 720000 120000 50000 60000 130000 50000 1200000 150000 3 5000000 7 5000000 30 63000000 24
Выходные данные #1
Case 1: 120000 Case 2: 110000 Case 3: IMPOSSIBLE