놋쇠 벽돌 배합하기

한 공장이 놋쇠 벽돌을 만든다. 놋쇠는 구리와 아연의 합금이며, 벽돌 하나의 무게는 정확히 $1000$그램이고 그중 구리 함량은 $1$그램부터 $999$그램까지가 될 수 있다. 공장은 서로 다른 $N$가지 종류의 벽돌을 만들며, 각 종류는 고유한 구리 함량과 가격을 가지고 카탈로그에 실려 있다.

손님은 정확히 $M$개의 벽돌을 사려고 하는데, 이들은 모두 서로 다른 종류여야 한다. 고른 벽돌들을 함께 녹이면, 그 혼합물은 킬로그램당 구리 함량이 최소 $C_{min}$그램 이상, 최대 $C_{max}$그램 이하가 되어야 한다. 벽돌 하나가 정확히 $1$킬로그램이므로 $M$개를 녹이면 $M$킬로그램이 되고, 전체 구리량은 고른 구리 함량의 합과 같다. 따라서 조건은 다음과 같다.

$M \cdot C_{min} \le (\text{고른 벽돌들의 구리 함량 합}) \le M \cdot C_{max}.$

이 조건을 만족하는 모든 선택 중에서 손님은 총가격이 가장 작은 것을 원한다. 각 손님에 대해 그 최소 총가격을 구하여라. $M$, $C_{min}$, $C_{max}$ 값은 손님마다 다르다.

첫째 줄에는 벽돌 종류의 수 $N$ ($1 \le N \le 200$)이 주어진다. 이어지는 $N$개의 줄에는 각 벽돌 종류의 구리 함량($1$부터 $999$그램)과 가격(센트 단위) 두 정수가 주어진다. 어떤 벽돌도 $1000$센트를 넘지 않는다.

그다음 줄에는 손님의 수 $C$ ($1 \le C \le 100$)가 주어진다. 이어지는 $C$개의 줄에는 각 손님의 요청을 나타내는 세 정수 $M$, $C_{min}$, $C_{max}$ ($1 \le M \le 20$, $1 \le C_{min} \le 999$, $1 \le C_{max} \le 999$)가 주어진다.

입력의 모든 수는 양의 정수이다.

각 손님에 대해, 조건을 만족하도록 서로 다른 $M$가지 벽돌 종류를 고를 때의 최소 총가격(센트 단위)을 한 줄에 하나씩 출력한다. 조건을 만족하는 선택이 없으면 그 손님에 대해 impossible을 출력한다.