The city planners plan to build N plants in the city which has M shops.
Each shop needs products from some plants to make profit of $pro_i$ units.
Building ith plant needs investment of $pay_i$ units and it takes $t_i$ days.
Two or more plants can be built simultaneously, so that the time for building multiple plants is maximum of their periods($t_i$).
You should make a plan to make profit of at least L units in the shortest period.
输入解释
First line contains T, a number of test cases.
For each test case, there are three integers N, M, L described above.
And there are N lines and each line contains two integers $pay_i$, $t_i$(1<= i <= N).
Last there are M lines and for each line, first integer is $pro_i$, and there is an integer k and next k integers are index of plants which can produce material to make profit for the shop.
1 <= T <= 30 1 <= N, M <= 200 $1 \leq L, t_i \leq 1000000000$ $1 \leq pay_i, pro_i \leq 30000$
输出解释
For each test case, first line contains a line “Case #x: t p”, x is the number of the case, t is the shortest period and p is maximum profit in t hours. You should minimize t first and then maximize p.
If this plan is impossible, you should print “Case #x: impossible”