Less Time, More profit

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”

2

1 1 2
1 5
3 1 1

1 1 3
1 5
3 1 1

Case #1: 5 2
Case #2: impossible

金策工业综合大学（DPRK）

2016 Multi-University Training Contest 9