시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 38 13 13 34.211%

문제

댐은 n개의 수문을 가지고 있다. 각각의 수문은 자체 용량과 물길을 가지고 있고, 하류에 영향을 줄 수 있다. 

수문이 열렸을 때, 영향을 받는 지역은 홍수의 위험이 있다. 수문에 의한 예상 피해액은 지역의 인구의 수와 면적으로 계산할 수 있다.

수문 Gi의 유량이 Fi m3/hour 이고, 피해 비용이 Ci라고 하자. 댐에는 물이 Vm3 만큼 저장되어 있고, 이 물을 T시간 이내에 모두 비워내야 하는 상황이다. 이 때, 수문을 어떻게 열어야 피해 비용이 최소가 되는지를 구하는 프로그램을 작성하시오.

예를 들어, 댐에 수문이 4개가 있고, 각 수문의 유량과 피해 비용이 아래와 같다고 하자.

수문 G1 G2 G3 G4
유량 (m3/hour) 720,000 50,000 130,000 1,200,000
비용 120,000 60,000 50,000 150,000

물 5백만 m3을 7시간 안에 비워내야 하는 경우에, G1을 7시간동안 열어 놓으면 되고, 비용은 120,000이 된다. 

물 5백만 m3을 30시간 안에 비워내야 하는 경우에는 G2를 29시간, G3를 28시간 동안 열어 놓으면 된다. 이 때의 비용은 110,000이 된다.

모든 수문은 항상 독립적으로 동작하며, 수문은 항상 1시간 단위만큼 열 수 있다.

입력

첫째 줄에 수문의 개수 n이 주어진다. (1 ≤ n ≤ 20) 다음 n개 줄에는 각 수문 Gi의 유량 (m3/hour) Fi와 피해 비용 Ci가 주어진다. 다음 줄에는 테스트 케이스의 수 m (1 ≤ m ≤ 50)이 주어진다. 다음 m개 줄에는 V와 T가 주어지며, 물 V m3을 T시간 이내에 비워내야 한다는 뜻이다. (1 ≤ Fi, V, Ci ≤ 109, 1 ≤ T ≤ 1000)

출력

각 테스트 케이스마다, 최소 비용을 예제 출력과 같이 출력한다. 만약 물 V를 T시간 이내에 비워낼 수 없으면 "IMPOSSIBLE"을 출력한다.

예제 입력

4
720000 120000
50000 60000
130000 50000
1200000 150000
3
5000000 7
5000000 30
63000000 24

예제 출력

Case 1: 120000
Case 2: 110000
Case 3: IMPOSSIBLE

힌트