With the end of the final exams, the annual course selection period has begun.

Little C is a diligent student who has set a small goal for himself: to earn at least $T$ credits in the new semester. According to the announcement from the Academic Affairs Office, there are $m$ categories of courses available, with $n_i$ courses in the $i$-th category. Based on the announcement, Little C has refined his goal: in addition to earning at least $T$ credits in total, he must earn at least $s_i$ credits from the $i$-th category ($i=1, 2, \dots, m$). Furthermore, being a clever student, Little C has calculated the credits earned and the mental effort required for each course. Not only that, he has discovered special relationships between some courses: taking two similar courses simultaneously may reduce the mental effort required; taking two very intensive courses simultaneously may increase the mental effort required; and if two courses have a time conflict, they cannot be taken together.

Little C wants to achieve his goal while spending the minimum amount of mental effort. Can you help Little C calculate the minimum mental effort required to reach his goal?

Input

The first line contains two positive integers $m$ and $T$, representing the number of categories and the total number of credits required.

The next $m$ sections contain the input for each category. For the $i$-th section:

The first line contains two non-negative integers $n_i$ and $s_i$, representing the number of courses in the $i$-th category and the credits required from that category.

The next $j+1$ lines ($1 \le j \le n_i$) each contain two positive integers $w_{i,j}$ and $c_{i,j}$, representing the credits earned and the mental effort required for the $j$-th course in the $i$-th category.

After the $m$ sections, there is a non-negative integer $p$, representing the number of relationships.

The next $p$ lines each describe a relationship. Each relationship can be represented in one of the following 3 forms (all input data below are positive integers):

• $1\ x_1\ y_1\ x_2\ y_2\ c$: Taking the $y_1$-th course of the $x_1$-th category and the $y_2$-th course of the $x_2$-th category simultaneously reduces the total mental effort by $c$.
• $2\ x_1\ y_1\ x_2\ y_2\ c$: Taking the $y_1$-th course of the $x_1$-th category and the $y_2$-th course of the $x_2$-th category simultaneously increases the total mental effort by $c$.
• $3\ x_1\ y_1\ x_2\ y_2$: The $y_1$-th course of the $x_1$-th category and the $y_2$-th course of the $x_2$-th category cannot be taken simultaneously.

Output

The output file contains a single integer representing the minimum mental effort required to achieve the goal. If it is impossible to reach Little C's goal, output $-1$.

Examples

Input 1

1 10
1 1
1 1
0

Output 1

-1

Note 1

Even if all courses are taken, the total credits still cannot meet Little C's requirement, so output $-1$.

Input 2

3 10
5 4
1 30
1 30
2 3
2 3
3 30
6 6
1 1
1 30
2 1
2 30
3 9
3 10
1 0
1 10
1
1 1 5 2 6 35

Output 2

10

Note 2

One possible selection is: in the first category, choose the 4th and 5th courses; in the second category, choose the 1st, 3rd, and 6th courses; in the third category, choose no courses (the selection is not unique).

Examples 3

See courses3.in and courses3.ans in the additional files.

Subtasks

Let $N=\sum_{i=1}^{m} n_i$, and $M$ be the maximum value of mental effort (including the increases or decreases from relationships).

For $5\%$ of the data: $N\le 5$.

For $10\%$ of the data: $N\le 15$.

An additional $10\%$ of the data: $N\le 1000$, $p=0$.

An additional $10\%$ of the data: $w_i=1$, $p=0$.

An additional $10\%$ of the data: $T=\sum_{i=1}^{m} s_i$, $p=0$.

An additional $10\%$ of the data: $N\le 10^4$, $M\le 50$, and courses with relationships are in the same category.

An additional $10\%$ of the data: $N\le 5\times 10^4$, $M\le 50$.

For $100\%$ of the data: $N\le 5\times 10^5$, $M\le 200$, $T-\sum_{i=1}^{m} s_i\le 40$, $m\le 5\times 10^4$, $w_{i,j}\in\{1,2,3\}$.

Let $P$ be the number of courses involved in at least one constraint; it is guaranteed that $P\le 12$ and $p\le \frac{P(P-1)}{2}$.

The data guarantees that there is at most one relationship between any two courses.