P8215 [THUPC 2022 Preliminary] Group Assignment

The teacher assigned a group project. Before that, the teacher had divided the $2n$ students in the class into $n$ groups, with two people in each group. Student $1$ and student $2$ are in one group, student $3$ and student $4$ are in one group, $\ldots$, and student $2n-1$ and student $2n$ are in one group. The teacher lets each team arrange the division of work by themselves. Whether they will cooperate becomes a big problem, so everyone decides to determine it by voting. First, each person decides whether they are willing to cooperate with their teammate. Different people have different willingness to cooperate due to their own reasons and the reasons related to their assigned teammate. For student $i$, choosing “willing” produces dissatisfaction $c_i$, and choosing “unwilling” produces dissatisfaction $d_i$. If both teammates choose “willing”, then depending on the actual situation they may cooperate or may not cooperate. However, if one teammate chooses “unwilling”, then they can only not cooperate. Among the students, there are also $m$ directed “like” relationships. Each relationship is of the form “$A$ likes $B$”. In such a relationship, if $A$ does not cooperate with their teammate and $B$ chooses “willing”, then $A$ will feel a bit upset and produce dissatisfaction $a_i$; if $A$ voted “unwilling” but $B$ successfully cooperates with their teammate, then $A$ will feel envy and produce dissatisfaction $b_i$. (Since this setting would become strange when $A$ and $B$ are in the same group, the problem guarantees that this will not happen.) Here $i$ denotes the $i$-th relationship. If a student $i$ chooses “willing” but their teammate chooses “unwilling”, then they will have dissatisfaction $e_i$ because of their teammate. Find the minimum possible total dissatisfaction over all cases.

The first line contains two integers $n, m$. The next $2n$ lines each contain three integers $c_i, d_i, e_i$. The next $m$ lines each contain four positive integers $A, B, a_i, b_i$.

Output one integer in one line, representing the answer.

Constraints It is guaranteed that $1 \le n \le 5000$, $0 \le m \le 10000$, and $1 \le a_i, b_i, c_i, d_i, e_i \le 10^9$. Translated by ChatGPT 5