P6731 [WC2020] Course Selection

### Reminder: Some of the current official testdata for this problem does not match the Constraints. **Let $P$ be the number of courses involved in the constraints. It is guaranteed that $P\leq12$.** **There is one test point that does not satisfy $T \geq \sum s_i$.**

With the end of final exams, the annual course selection period begins again. Student C is a good student who loves studying. He set a small goal for himself: to earn at least $T$ credits in the new semester. According to the announcement from the academic office, there are $m$ categories of courses to choose from this time, and the $i$-th category has $n_i$ courses. Based on the announcement, Student C raised his goal: on the basis of earning at least $T$ credits in total, he must also earn at least $s_i$ credits in each category $i$ ($i=1,2,\cdots,m$). Meanwhile, using his experience, Student C calculated the credits he can get from each course and the mental effort cost required. Moreover, he discovered that some courses have special relationships: taking two similar courses together may reduce the mental effort cost; taking two very demanding courses together may increase the cost; and if two courses have a time conflict, they cannot be taken together. Student C wants to spend the minimum total mental effort to reach his goal. Can you help him compute the minimum mental effort needed?

The first line contains two positive integers $m,T$, representing the number of categories and the total credits required. Then follow $m$ blocks of input. For the $i$-th block: The first line contains two non-negative integers $n_i,s_i$, representing the number of courses in the $i$-th category and the minimum credits required in this category. The $j+1$-th line ($1\le j\le n_i$) contains two positive integers $w_{i,j},c_{i,j}$, representing the credits gained by taking the $j$-th course in category $i$, and the mental effort cost required. After the $m$ blocks, there is a non-negative integer $p$, representing the number of relationships. The next $p$ lines each describe one relationship. Each relationship is one of the following 3 types (all numbers below are positive integers): $1\ x_1\ y_1\ x_2\ y_2\ c$: taking the $y_1$-th course in category $x_1$ and the $y_2$-th course in category $x_2$ together can reduce the cost by $c$. $2\ x_1\ y_1\ x_2\ y_2\ c$: taking the $y_1$-th course in category $x_1$ and the $y_2$-th course in category $x_2$ together will increase the cost by $c$. $3\ x_1\ y_1\ x_2\ y_2$: the $y_1$-th course in category $x_1$ and the $y_2$-th course in category $x_2$ cannot be taken together.

The output contains only one line with one integer, representing the minimum mental effort required to reach the goal. If it is impossible to reach Student C's goal, output `-1`.

#### Explanation for Sample 1 Even if all courses are taken, the total credits still cannot meet Student C's requirement, so the output is `-1`. #### Explanation for Sample 2 One possible selection is: choose courses 4 and 5 in the first category, choose courses 1, 3, and 6 in the second category, and choose no courses in the third category (the selection is not unique). #### Constraints Let $N=\sum_{i=1}^{m} n_i$, and let $M$ be the maximum mental effort cost (including increases or decreases caused by related courses). For $5\%$ of the data: $N\le 5$. For $10\%$ of the data: $N\le 15$. For another $10\%$ of the data: $N\le 1000$, $p=0$. For another $10\%$ of the data: $w_i=1$, $p=0$. For another $10\%$ of the data: $T=\sum_{i=1}^{m} s_i$, $p=0$. For another $10\%$ of the data: $N\le 10^4$, $M\le 50$, and related courses are within the same category. For another $10\%$ of the data: $N\le 5\times 10^4$, $M\le 50$. For $100\%$ of the data: $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\}$. **The official data is incorrect. According to testing, the maximum $p$ is $66$.** The data guarantees that for any two courses, there is at most one relationship between them. Translated by ChatGPT 5