Mr. Panda and Crystal

Long long time ago, there is a magic continent far far away.
There are N types of magic crystals that contain ancient magic powers. Each of the type of magic crystal has its own price for one piece in the market. As the most powerful magician, Mr. Panda could synthesize some types of crystals by collecting some amount of other types of crystals. He could also create some types of crystals by using some number of his magic powers.
Now, Mr Panda can create any number of crystals as he wish by using no more than M magic powers. He want to know the maximum amount of money he can make by sell all the crytals he creates and synthesizes.

The first line of the input gives the number of test cases, T. T test cases follow.
Each test case starts with 3 positive intergers, M, N and K represent the amount of magic powers Mr. Panda had, the number of crystal types on the magic continent and the number of crystal synthesis equations.
Then N lines follows, each of them starts with one 0 or 1 which indicates whehter Mr. Panda could create this type of crystal.
If the $i^{th}$ line starts with 0, which means Mr. Panda couldn’t create crystal type i. Then there is one integer $p_i$ in this line which is the price for each piece of crystal type i.
If the $i^{th}$ line starts with 1, which means Mr. Panda could create crystal type i. Then there are two positive integers $c_i$ and $p_i$ in this line, the first is the amout of magic power cost when creates one piece of crystal type i, and the second is is the price for each piece of crystal type i.
The following K lines each start with two interger $x_i$ and $y_i$ , which means for synthesizing one piece of crystal type $x_i$ , $y_i$ rules should be satisfied. Then there are $y_i$ pair of positive intergers $u_j$ and $v_j$ means for one piece of $x^{th}_{i}$ type cristal, we have to collect $v_i$ piece of crystal type $u_i$. Only when all the rules of $u_i$ and $v_i$ are satisfied, Mr. Panda could synthesize one piece $x^{th}_{i}$ type cristal.

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the maximum amout of money Mr. Panda could make.

limits

$\bullet 1 ≤ T ≤ 100.$
$\bullet 1 ≤ M ≤ 10000.$
$\bullet 1 ≤ N ≤ 200.$
$\bullet 1 ≤ K ≤ 200.$
$\bullet 1 ≤ x_i, u_j ≤ N.$
$\bullet for each crystal synthesis equation, all uj are different.$
$\bullet 1 ≤ v_j ≤ 100.$
$\bullet 1 ≤ c_i , p_i ≤ 10000.$

2
100 3 2
0 20
1 15 10
1 2 1
1 2 2 1 3 1
2 1 3 2
100 3 2
1 3 1
1 4 1
0 10
3 1 1 3
3 1 2 2

Case #1: 330
Case #2: 121

2016 CCPC-Final