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 $g o a l$ 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 <= T <= 100)$ test cases in this problem.
For every test cases,the first line has three integers $N (1 <= N <= 20)$, $M (1 <= M <= 100)$, $g o a l (1 <= g o a l <= 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 <= p_i <= 5)$,$o p_i (1 <= o p_i <= 5)$,$k_i (1 <= k_i <= 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_{i j} (1 <= b_{i j} <= 5)$,$c_{i j} (1 <= c_{i j} <= 9)$,indicating that it takes $c_{i j}$ type $b_{i j}$ 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 <= q_i <= 5)$,$b_i (1 <= p_i <= 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_{i j} (1 <= d_{i j} <= 5)$,$e_{i j} (1 <= e_{i j} <= 9)$,indicating that the pirate needs to find that you have at least $e_{i j}$ of type $d_{i j}$ to come to you. Promised that all $b_{i j}$,$d_{i j}$ in one gem card or one pirate are different.
For every test case, output the answer in a line.
## Input
White, blue, red, green and black correspond to $1$,$2$,$3$,$4$,$5$ There are $T (1 <= T <= 100)$ test cases in this problem.For every test cases,the first line has three integers $N (1 <= N <= 20)$, $M (1 <= M <= 100)$, $g o a l (1 <= g o a l <= 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 <= p_i <= 5)$,$o p_i (1 <= o p_i <= 5)$,$k_i (1 <= k_i <= 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_{i j} (1 <= b_{i j} <= 5)$,$c_{i j} (1 <= c_{i j} <= 9)$,indicating that it takes $c_{i j}$ type $b_{i j}$ 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 <= q_i <= 5)$,$b_i (1 <= p_i <= 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_{i j} (1 <= d_{i j} <= 5)$,$e_{i j} (1 <= e_{i j} <= 9)$,indicating that the pirate needs to find that you have at least $e_{i j}$ of type $d_{i j}$ to come to you. Promised that all $b_{i j}$,$d_{i j}$ in one gem card or one pirate are different.
## Output
For every test case, output the answer in a line.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ K = (x_0, y_0) \in \mathbb{Z}^2 $ be the initial position of the Kin.
- Let $ n \in \mathbb{Z}^+ $ be the number of Fu.
- Let $ F_i = (x_i, y_i) \in \mathbb{Z}^2 $ for $ i \in \{1, \dots, n\} $ be the initial positions of the Fu, all distinct.
**Constraints**
1. $ 1 \le T \le 10 $
2. $ 1 \le n \le 1000 $, $ \sum n \le 5000 $
3. $ |x_0|, |y_0|, |x_i|, |y_i| \le 10^9 $
4. $ (x_i, y_i) \ne (x_j, y_j) $ for all $ i \ne j $
**Movement Rules**
- Kin can move in one step to any of:
$$
\{(x \pm 1, y), (x, y \pm 1), (x \pm 1, y + 1)\}
$$
(6 possible moves; note: only upward and lateral moves, no downward).
- Each Fu moves **only** downward: $ (x_i, y_i) \to (x_i, y_i - 1) $ per turn.
- Turns alternate: Kin moves first, then all Fu move simultaneously.
- Kin defeats a Fu if it lands on its position during Kin’s move.
- Opponent is defeated if a Fu moves onto Kin’s position during Fu’s move.
**Objective**
Maximize the number of Fu defeated by Kin before any Fu reaches Kin’s position or Kin is captured.
**Key Insight**
A Fu at $ (x_i, y_i) $ will reach row $ y = y_0 $ after $ d_i = y_i - y_0 $ turns (if $ y_i \ge y_0 $).
Kin must reach $ (x_i, y_i - t) $ at turn $ t $ to capture it, where $ t \le y_i - y_0 $.
Kin’s Manhattan-like distance to $ (x_i, y_i - t) $ must be $ \le t $.
Define for each Fu $ i $:
Let $ t_i = y_i - y_0 $ be the number of turns until Fu $ i $ reaches Kin’s initial y-level.
Kin can capture Fu $ i $ at turn $ t \le t_i $ if:
$$
\max(|x_i - x_0|, y_i - y_0 - t) \le t \quad \text{and} \quad t \le t_i
$$
But simpler: Kin can reach $ (x_i, y_i - t) $ in $ t $ steps if:
$$
|x_i - x_0| + |(y_i - t) - y_0| \le t \quad \text{(Manhattan)}
\Rightarrow |x_i - x_0| + (y_i - y_0 - t) \le t
\Rightarrow |x_i - x_0| + (y_i - y_0) \le 2t
\Rightarrow t \ge \frac{|x_i - x_0| + y_i - y_0}{2}
$$
And $ t \le y_i - y_0 $.
So Fu $ i $ is capturable iff:
$$
\frac{|x_i - x_0| + y_i - y_0}{2} \le y_i - y_0
\quad \text{and} \quad
y_i \ge y_0
$$
Simplify:
$$
|x_i - x_0| + y_i - y_0 \le 2(y_i - y_0)
\Rightarrow |x_i - x_0| \le y_i - y_0
$$
Thus, **Fu $ i $ is capturable if and only if**:
$$
y_i \ge y_0 \quad \text{and} \quad |x_i - x_0| \le y_i - y_0
$$
**Objective Reformulated**
Count the number of Fu satisfying:
$$
y_i \ge y_0 \quad \text{and} \quad |x_i - x_0| \le y_i - y_0
$$
This is the maximum number of Fu Kin can defeat.
**Answer**
For each test case, output:
$$
\left| \left\{ i \in \{1, \dots, n\} \mid y_i \ge y_0 \text{ and } |x_i - x_0| \le y_i - y_0 \right\} \right|
$$