问题文

某个班级里有 $N$ 个女生和 $M$ 个男生。女生们有从 $1$ 到 $N$ 的出席号码，男生们有从 $1$ 到 $M$ 的出席号码。

幸运的丘比特要从这里选择 $P$ 个女生和 $Q$ 个男生组成一个旅行团。

这 $N$ 个女生一共拥有 $R$ 个巧克力，每个巧克力都有从 $1$ 到 $R$ 的编号。

编号为 $i (1≦i≦R)$ 的巧克力由拥有出席号码 $x_i$ 的女生持有，并计划在旅行途中交给出席号码为 $y_i$ 的男生。因此，只有当旅行团中同时包含了出席号码为 $x_i$ 的女生和出席号码为 $y_i$ 的男生时，巧克力 $i$ 才可以被交付。巧克力 $i$ 被顺利交付的幸福度为 $z_i$。

作为被成功交付的巧克力所带来的幸福度的总和，最大能达到多少？

输入

从标准输入中以以下格式给出输入。

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

• 第 $1$ 行有 $5$ 个整数，用空格分隔开：$N (1≦N≦18)$, $M (1≦M≦18)$, $P (1≦P≦N)$, $Q (1≦Q≦M)$, $R (1≦R≦N×M)$。表示班级中女生的数量为 $N$，男生的数量为 $M$，旅行团包含 $P$ 个女生和 $Q$ 个男生，巧克力的数量为 $R$。
• 第 $2$ 行到第 $R$ 行给出了与巧克力相关的信息。在这 $R$ 行中，第 $i (1≦i≦R)$ 行有 $3$ 个整数 $x_i (1≦x_i≦N)$, $y_i (1≦y_i≦M)$, $z_i (1≦z_i≦10,000)$，用空格分隔开。表示巧克力 $i$ 由出席号码为 $x_i$ 的女生持有，计划在旅行途中交给出席号码为 $y_i$ 的男生，并且巧克力 $i$ 的幸福度为 $z_i$。
• 对于整数 $i$ 和 $j$，满足 $1≦i＜j≦R$，要么 $x_i≠x_j$，要么 $y_i≠y_j$。

部分得分

此问题设置了部分得分。

• 如果满足 $N≦8$ 和 $M≦8$ 的数据集 $1$，则可以获得 $30$ 分。

输出

请以一行输出作为被成功交付的巧克力所带来的幸福度的总和的最大值。(21:51 表达方式更改)输出末尾应有换行符。

输入例1

3 4 2 3 7
1 1 9
1 2 7
1 3 15
1 4 6
2 2 3
2 4 6
3 3 6

输出例1

37

我们考虑由出席号码为 $1$ 和 $2$ 的女生，以及出席号码为 $2$, $3$, $4$ 的男生组成的旅行团。

• 巧克力 $1$ 由出席号码为 $1$ 的男生不参加旅行，因此不会交付。
• 巧克力 $2$ 将被交付给旅行中同时包含出席号码为 $1$ 的女生和出席号码为 $2$ 的男生。巧克力的幸福度为 $7$。
• 巧克力 $3$ 将被交付给旅行中同时包含出席号码为 $1$ 的女生和出席号码为 $3$ 的男生。巧克力的幸福度为 $15$。
• 巧克力 $4$ 将被交付给旅行中同时包含出席号码为 $1$ 的女生和出席号码为 $4$ 的男生。巧克力的幸福度为 $6$。
• 巧克力 $5$ 将被交付给旅行中同时包含出席号码为 $2$ 的女生和出席号码为 $2$ 的男生。巧克力的幸福度为 $3$。
• 巧克力 $6$ 将被交付给旅行中同时包含出席号码为 $2$ 的女生和出席号码为 $4$ 的男生。巧克力的幸福度为 $6$。
• 巧克力 $7$ 由出席号码为 $3$ 的女生不参加旅行，因此不会交付。

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

输入例2

4 5 3 2 9
2 3 5
3 1 4
2 2 2
4 1 9
3 5 3
3 3 8
1 4 5
1 5 7
2 4 8

输出例2

26