AT_abc018_4.[ABC018D] バレンタインデー

某班级有 $N$ 名女生和 $M$ 名男生。女生的出席编号为 $1$ 到 $N$，男生的出席编号为 $1$ 到 $M$。

幸运的丘比特要从中选出 $P$ 名女生和 $Q$ 名男生，组成一个旅行小组。

这 $N$ 名女生总共持有 $R$ 盒巧克力，每盒巧克力编号为 $1$ 到 $R$。

第 $i$ 盒巧克力（$1 \leq i \leq R$）由出席编号为 $x_i$ 的女生持有，计划在旅行中送给出席编号为 $y_i$ 的男生。因此，只有当旅行小组中同时包含出席编号为 $x_i$ 的女生和出席编号为 $y_i$ 的男生时，这盒巧克力才能顺利送出。如果巧克力 $i$ 顺利送出，则会获得 $z_i$ 的幸福度。

请问，能够获得的巧克力幸福度总和的最大值是多少。

输入通过标准输入给出，格式如下：

$N$ $M$ $P$ $Q$ $R$
$x_1$ $y_1$ $z_1$
$x_2$ $y_2$ $z_2$
$\vdots$
$x_R$ $y_R$ $z_R$

• 第 $1$ 行包含 $5$ 个整数 $N\ (1 \leq N \leq 18)$，$M\ (1 \leq M \leq 18)$，$P\ (1 \leq P \leq N)$，$Q\ (1 \leq Q \leq M)$，$R\ (1 \leq R \leq N \times M)$，表示班级中有 $N$ 名女生、$M$ 名男生，旅行小组由 $P$ 名女生和 $Q$ 名男生组成，共有 $R$ 盒巧克力。
• 接下来的 $R$ 行，每行包含 $3$ 个整数 $x_i\ (1 \leq x_i \leq N)$，$y_i\ (1 \leq y_i \leq M)$，$z_i\ (1 \leq z_i \leq 10,000)$，表示第 $i$ 盒巧克力由出席编号为 $x_i$ 的女生持有，计划送给出席编号为 $y_i$ 的男生，该巧克力的幸福度为 $z_i$。
• 对于任意 $1 \leq i < j \leq R$，都有 $x_i \neq x_j$ 或 $y_i \neq y_j$。

请输出能够获得的巧克力幸福度总和的最大值。输出应为一行，并以换行符结尾。

部分分

本题设有部分分。

• 若能正确解决 $N \leq 8$ 且 $M \leq 8$ 的数据集 $1$，可获得 $30$ 分。

样例解释 1

考虑由出席编号为 $1$、$2$ 的女生和出席编号为 $2$、$3$、$4$ 的男生组成的旅行小组。

• 巧克力 $1$ 由于出席编号为 $1$ 的男生未参加旅行，无法送出。
• 巧克力 $2$ 的赠送双方均在旅行小组中，可以顺利送出，幸福度为 $7$。
• 巧克力 $3$ 的赠送双方均在旅行小组中，可以顺利送出，幸福度为 $15$。
• 巧克力 $4$ 的赠送双方均在旅行小组中，可以顺利送出，幸福度为 $6$。
• 巧克力 $5$ 的赠送双方均在旅行小组中，可以顺利送出，幸福度为 $3$。
• 巧克力 $6$ 的赠送双方均在旅行小组中，可以顺利送出，幸福度为 $6$。
• 巧克力 $7$ 由于出席编号为 $3$ 的女生未参加旅行，无法送出。

幸福度总和为 $7 + 15 + 6 + 3 + 6 = 37$，这是最大值。

由 ChatGPT 4.1 翻译