Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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.

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, 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$

提交代码