[WC2020] 选课
题目背景
### 提醒:
本题目前的官方数据有部分与数据范围不符。
**令 $P$ 为限制涉及到的课程数目,保证 $P\leq12$。**
**有一个测试点不满足 $T \geq \sum s_i$。**
题目描述
随着期末考试的结束,一年一度的选课环节又拉开了帷幕。
小 C 是一个热爱学习的好学生,他给自己定了一个小目标:在新的学期至少修够 $T$ 学分。从教务处给出的公告上看,本次可供选择的课程一共有 $m$ 种分类,第 $i$ 种分类中有 $n_i$ 门课程。小 C 根据公告的内容,提高了自己的学习目标:在所有课程至少修满 $T$ 学分的基础上,第 $i$ 种分类($i=1,2,\cdots,m$)至少修够 $s_i$ 的学分。同时,聪明的小 C 凭借自己的经验,计算出了学习每门课程所能得到的学分和所需要消耗的脑力值。不仅如此,他还发现,有些课程之间存在特殊的关系:同时学习某两门内容相似的课程,可能会减少脑力值的消耗;同时学习某两门十分硬核的课,可能会增加脑力值的消耗;某两门课程时间冲突,则无法同时学习。
小 C 希望能够花费最少的脑力值来达到他的目标。你能帮小 C 计算出达到目标所需要的最小脑力值吗?
输入输出格式
输入格式
第一行两个正整数 $m,T$,表示分类种数和总共需要修够的学分数。
接下来 $m$ 段输入,对于第 $i$ 段输入:
第一行有两个非负整数 $n_i,s_i$,表示第 $i$ 种分类的所有课程数和需要修够的学分。
第 $j+1$($1\le j\le n_i$)行有两个正整数 $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
1 10
1 1
1 1
0
输出样例 #1
-1
输入样例 #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
输出样例 #2
10
说明
#### 样例1解释
即使学习所有课程,总学分仍无法达到小 C 的要求,故输出 `-1`。
#### 样例2解释
一种可能的选法为:第一种分类中选择第 4、5 门课,第二种分类选择第 1、3、6 门课,第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$,$0\le T-\sum_{i=1}^{m} s_i\le 40$,$m\le 5\times 10^4$,$p\le 12$,$w_{i,j}\in\{1,2,3\}$。
**官方数据有误,经测试,$p$ 最大为 $66$**
数据保证任意两种课程至多只有一种关系。