由于本题官方数据不符合题面中的数据范围，因此本题仅公开题面，请不要在本题提交程序

如果需要在官方数据下测评，可以右转隔壁LOJ

修改了数据范围部分。

LOJ提交链接

随着期末考试的结束，一年一度的选课环节又拉开了帷幕。

小 C 是一个热爱学习的好学生，他给自己定了一个小目标：在新的学期至少修够 $T$ 学分。从教务处给出的公告上看，本次可供选择的课程一共有 $m$ 种分类，第 $i$ 种分类中有 $n_i$ 门课程。小 C 根据公告的内容，提高了自己的学习目标：在所有课程至少修满 $T$ 学分的基础上，第 $i$ 种分类$（i=1,2,\cdots,m)$至少修够 $s_i$ 的学分。同时，聪明的小 C 凭借自己的经验，计算出了学习每门课程所能得到的学分和所需要消耗的脑力值。不仅如此，他还发现，有些课程之间存在特殊的关系：同时学习某两门内容相似的课程，可能会减少脑力值的消耗；同时学习某两门十分硬核的课，可能会增加脑力值的消耗；某两门课程时间冲突，则无法同时学习。

小 C 希望能够花费最少的脑力值来达到他的目标。你能帮小 C 计算出达到目标所需要的最小脑力值吗？

输入格式

第一行两个正整数 $m,T$，表示分类种数和总共需要修够的学分数。

接下来 $m$ 段输入，对于第 $i$ 段输入：

第 1 行有两个非负整数 $n_i,s_i$，表示第 $i$ 种分类的所有课程数和需要修够的学分。

第 $j+1(1\le j\le n_i)$ 行有 2 个正整数 $w_{i,j},c_{i,j}$ 表示选修第 $i$ 种分类中的第 $j$ 门课能获得的学分和需要消耗的脑力。

$m$ 段输入之后，有一个非负整数 $p$，表示关系的条数。

接下来 $p$ 行每行一条关系，每一条关系可表示为以下 3 种形式之一（以下所有输入数据均为正整数）：

$1\ x_1\ y_1\ x_2\ y_2\ c$，表示同时修第 $x_1$ 种分类中的第 $y_1$ 门课和第 $x_2$ 种分类中的第 $y_2$ 门课，可以减少 $c$ 的消耗。

$2\ x_1\ y_1\ x_2\ y_2\ c$，表示同时修第 $x_1$ 种分类中的第 $y_1$ 门课和第 $x_2$ 种分类中的第 $y_2$ 门课，需要增加 $c$ 的消耗。

$3\ x_1\ y_1\ x_2\ y_2$，表示第 $x_1$ 种分类中的第 $y_1$ 门课和第 $x_2$ 种分类中的第 $y_2$ 门课不能同时修。

输出格式

输出文件只有一行，包含一个整数，表示达到目标所需要的最小脑力值。如果无法达到小 C 的目标，请输出 -1。

1 10
1 1
1 1
0

-1

expanation

即使学习所有课程，总学分仍无法达到小 C 的要求，故输出 -1。

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

10

一种可能的选法为：第一种分类中选择第 4、5 门课，第二种分类选择第 1、3、6 门课，第3种分类不选课程（选法不唯一）。

样例3

见附加文件。

数据范围

设 $N=\sum_{i=1}^{m} n_i$,$M$ 为消耗脑力值的最大值（包括有关系的课程中增加或减少的消耗）。

对于 $5\%$ 的数据：$N\le 5$。

对于 $10\%$ 的数据：$N\le 15$。

有另外 $10\%$ 的数据：$N\le 1000,p=0$。

有另外 $10\%$ 的数据：$w_i=1,p=0$。

有另外 $10\%$ 的数据：$T=\sum_{i=1}^{m} s_i,p=0$。

有另外 $10\%$ 的数据：$N\le 10^4,M\le 50$，且有关系的课程在同一分类中。

有另外 $10\%$ 的数据：$N\le 5 \times 10^4,M\le 50$，

对于 $100\%$ 的数据：$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\}$。

修正：官方数据有一个测试点并没有满足 $0\le T-\sum_{i=1}^{m} s_i$ 这一条件。
记 $P$ 为至少涉及一个限制的课程，那么保证 $P\le 12, p\le \frac{P(P-1)}{2}$。

数据保证任意两种课程至多只有一种关系。

时间限制: $1\texttt{s}$

空间限制: $512\texttt{MB}$