cho.sh연구초미니
문제코드
문제 설명
시간 제한
메모리 제한
댐은 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"을 출력한다.