問題文
一个班有一个女孩。 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 时的幸福度为 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 。 一个整数
- 1 ≦ i < j ≦ R 对于 i,j ,x_i≠x_j 或 y_i≠y_j 成立。
部分点
针对此问题设置了部分分数。
- N ≦ 8 和 满足 M ≦ 8 的数据集 如果您正确回答 1 ,30 点。 如果您对除上述数据集之外的所有满足
出力
安全交付的巧克力所带来的最大可能的幸福总价值。 在 1 行输出。 (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 将被安全移交,因为收到它的男人和女人都将参加这次旅行。巧克力的幸福 7 。
- 巧克力 3 将被安全移交,因为收到它的男人和女人都将参加这次旅行。巧克力的幸福 15 。
- 巧克力 4 将被安全移交,因为收到它的男人和女人都将参加这次旅行。巧克力的幸福 6 。
- 巧克力 5 将被安全移交,因为收到它的男人和女人都将参加这次旅行。巧克力的幸福 3 。
- 巧克力 6 将被安全移交,因为收到它的男人和女人都将参加这次旅行。巧克力的幸福 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