← 返回题目列表

AtCoder · abc018_4

D. 情人节

中文机器翻译题面 查看原题

問題文

一个班有一个女孩。 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