3447. [CTSC 2020]选课

【题目描述】

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

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

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

【输入格式】

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

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

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

第j+1(1≤j≤ni)行有2个正整数wij,cij,表示选修第i种分类中的第j门课能获得的学分和需要消耗的脑力。

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

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

1 x1 y1 x2 y2 c,表示同时修第x1种分类中的第y1门课和第x2种分类中的第y2门课，可以减少c的消耗。

2 x1 y1 x2 y2 c,表示同时修第x1种分类中的第y1门课和第x2种分类中的第y2门课，需要增加c的消耗。

3 x1 y1 x2 y2,表示第x1种分类中的第y1门课和第x2种分类中的第y2门课不能同时修。

【输出格式】

只有一行，包含一个整数，表示达到目标所需要的最小脑力值。如果无法达到小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种分类不选课程（选法不唯一）。

【提示】

【来源】

在此键入。