题目描述

你受雇于一家生产黄铜砖的工厂的几位客户。黄铜是铜和锌的合金；每块砖重1000克，一块砖的铜含量范围可以从1克到999克。（请注意，铜含量低于55%或高于62%的黄铜实际上没什么用处；然而，这对于本题来说无关紧要）该工厂通过各种工艺生产不同类型的砖，每种砖都有不同的铜浓度和价格。它向客户分发这些砖类型的目录。

你的客户想要购买一定数量（$M$）的砖，由于某些宗教原因，这些砖必须是不同类型的。它们将被一起熔化，最终的混合物每千克必须具有至少$CMin$克且至多$CMax$克的铜浓度。他们的目标是挑选出$M$种类型的砖，使得混合物具有正确的浓度，并且这批砖的总价格最小化。你必须弄清楚如何做到这一点。$M$、$CMin$和$CMax$的值会因客户而异。

输入

输入的第一部分是包含一个数字$N$（$1 \leq N \leq 200$）的一行，$N$表示砖的类型数量，然后是$N$行，每行包含每种砖类型的铜浓度（在1到999之间）和价格（以美分为单位）。没有一块砖的价格超过10美元。

输入的第二部分是包含一个数字$C$（$1 \leq C \leq 100$）的一行，$C$表示你要服务的客户数量，接着是$C$行，每行包含每个客户的$M$（$1 \leq M \leq 20$）、$CMin$（$1 \leq CMin \leq 999$）和$CMax$（$1 \leq CMax \leq 999$）。

所有输入的数字都是正整数。

输出

对于每个客户，输出一行，包含他们为满足需求而购买砖的最小可能价格。如果没有办法满足他们的规格要求，则输出“impossible”。

输入数据 1

11
550 300
550 200
700 340
300 140
600 780
930 785
730 280
678 420
999 900
485 390
888 800
3
2 500 620
9 550 590
9 610 620

输出数据 1

420
impossible
3635

题目来源

Waterloo local 1999.06.19