#3331. 「WC2020」选课

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

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

小 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) 行有两个正整数 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

样例解释 1

即使学习所有课程,总学分仍无法达到小 C 的要求,故输出 -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

样例解释 2

一种可能的选法为:第一种分类中选择第 4 5 门课,第二种分类选择第 1 3 6 门课,第三种分类不选课程(选法不唯一)。

样例 3

见附加文件中的 courses3.incourses3.ans

数据范围与提示

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 \color{red}{0\le} T-\sum_{i=1}^{m} s_i\le 40 m\le 5\times 10^4 \color{red} {p \le 12} 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}

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