수문

댐에는 수문이 $n$개 있다. 각 수문은 고유한 유량과 물길을 가지며, 열리면 하류 지역에 홍수 피해를 줄 수 있다.

수문 $G_i$를 열면 시간당 $F_i$ m³의 물이 빠져나가고, 이로 인한 피해 비용은 $C_i$이다. 이 피해 비용은 수문을 여는 시간과 무관하게, 수문을 한 번이라도 열면 발생하는 고정 비용이다.

댐에는 물이 $V$ m³ 저장되어 있으며, 이 물을 모두 $T$시간 이내에 빼내야 한다. 피해 비용의 합이 최소가 되도록 수문을 여는 방법을 구하는 프로그램을 작성하시오.

각 수문은 서로 독립적으로 동작하고, 여는 시간은 정수 시간 단위이며 최대 $T$시간까지 열 수 있다. 따라서 수문 $G_i$를 열면 최대 $F_i \times T$ m³의 물을 빼낼 수 있다.

예를 들어 수문이 4개 있고 각 수문의 유량과 피해 비용이 다음과 같다고 하자.

물 5000000 m³를 7시간 이내에 빼내야 한다면, $G_1$만 열어도 $720000 \times 7 = 5040000$ m³를 빼낼 수 있으므로 충분하며, 비용은 120000이다.

물 5000000 m³를 30시간 이내에 빼내야 한다면, $G_2$와 $G_3$을 함께 열면 시간당 180000 m³를 빼낼 수 있어 30시간 안에 충분히 빼낼 수 있고, 비용은 $60000 + 50000 = 110000$이다.

첫째 줄에 수문의 개수 $n$이 주어진다. ($1 \le n \le 20$)

다음 $n$개의 줄에는 각 수문 $G_i$의 유량 $F_i$(m³/hour)와 피해 비용 $C_i$가 공백으로 구분되어 주어진다.

그다음 줄에는 질의의 개수 $m$이 주어진다. ($1 \le m \le 50$)

이어지는 $m$개의 줄에는 각 질의의 $V$와 $T$가 주어지며, 저장된 물 $V$ m³를 $T$시간 이내에 모두 빼내야 함을 뜻한다.

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

각 질의마다 한 줄에 Case k: X 형식으로 출력한다. 여기서 $k$는 1부터 시작하는 질의 번호이고, $X$는 최소 피해 비용이다. 만약 물 $V$를 $T$시간 이내에 모두 빼낼 수 없으면 $X$ 대신 IMPOSSIBLE을 출력한다.