Less Time, More profit

Problem Description

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.

Input

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$

Output

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”

Sample Input

2
1 1 2
1 5
3 1 1
1 1 3
1 5
3 1 1

Sample Output

Case #1: 5 2
Case #2: impossible

Author

金策工业综合大学（DPRK）

Source

2016 Multi-University Training Contest 9