P6731 [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 计算出达到目标所需要的最小脑力值吗？

无

无

#### 样例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$** 数据保证任意两种课程至多只有一种关系。