407478: GYM102801 F Splendor

Have you heard about Splendor's board game? We will adapt the process of this game. There are five colors of chips and gems in this game: white, blue, red, green and black. You start with zero chip.

There will be $$$N$$$ gem cards and $$$M$$$ pirates,Each gem card has three attributes,score,gem type,in exchange for the chips needed.

In each turn,you can exchange the corresponding chip for one card,then you will gain the score of this card and the gem on this card. (Once you have this card,you can't get the same card next time.)

But noticed: there can be no score in a gem card.

When the pirate observes that you have the type and number of gems he wants, the pirate will automatically come to you and you will receive the pirate's score.(Means that you will get bonus scores.) In each turn, you can do one of the three things:

1. Obtain any three different colored chips from the stack.

2. Obtain any two chips of the same color from the stack.

3. Exchange your chips for gems. Now, you have known all the gems and pirates.Your goal is to reach the minimum $$$goal$$$ score as soon as possible. How many turns does it take?(If you can't reach the minimum goal,you should output $$$-1$$$.)

White, blue, red, green and black correspond to $$$1$$$,$$$2$$$,$$$3$$$,$$$4$$$,$$$5$$$ There are $$$T(1 \leq T \leq 100)$$$ test cases in this problem.

For every test cases,the first line has three integers $$$N(1 \leq N \leq 20)$$$, $$$M(1 \leq M \leq 100)$$$, $$$goal(1 \leq goal \leq 40)$$$respectively representing the number of gems, the number of pirates, and the total score of the goal. The next $$$N$$$ rows starts with three integers,where the $$$i$$$ row starts with three integers $$$p_i(0 \leq p_i \leq 5)$$$,$$$op_i(1 \leq op_i \leq 5)$$$,$$$k_i(1 \leq k_i \leq 5)$$$, respectively representing the score of the $$$i$$$ gem card, the kind of gem, and the number of kinds of chips required.

Each row is followed by $$$k_i$$$ pairs of integers,$$$b_{ij}(1 \leq b_{ij} \leq 5)$$$,$$$c_{ij}(1 \leq c_{ij} \leq 9)$$$,indicating that it takes $$$c_{ij}$$$ type $$$b_{ij}$$$ chips to get this gem card. Next, there are $$$M$$$rows, each row represents a pirate's information, where the first row of $$$i$$$ has two integers $$$q_i(0 \leq q_i \leq 5)$$$,$$$b_i(1 \leq p_i \leq 5)$$$,indicating that the pirate's score is $$$q_i$$$, and the number of types of gems the player needs to own is $$$b_i$$$.

Each row is followed by $$$b_i$$$ pairs of integers,$$$d_{ij}(1 \leq d_{ij} \leq 5)$$$,$$$e_{ij}(1 \leq e_{ij} \leq 9)$$$,indicating that the pirate needs to find that you have at least $$$e_{ij}$$$ of type $$$d_{ij}$$$ to come to you. Promised that all $$$b_{ij}$$$,$$$d_{ij}$$$ in one gem card or one pirate are different.

For every test case, output the answer in a line.

1
12 4 15
3 3 4 4 3 1 3 5 3 2 5
4 2 1 1 7
4 5 3 3 6 5 3 4 3
5 4 2 2 7 4 3
1 1 3 2 3 3 3 1 2
2 1 2 3 5 5 3
2 2 2 1 5 2 3
1 1 3 3 2 5 2 4 3
0 1 3 4 2 5 1 2 2
0 4 1 3 3
0 5 3 2 2 3 1 1 2
0 4 1 5 4
3 2 1 4 2 4
3 3 1 3 2 3 4 3
3 3 4 3 3 3 5 3
3 2 2 4 4 4

17