← 返回题目列表

AtCoder · jsc2019_qual_e

E. 卡片收藏家

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

分数: 800 点

问题陈述

有 N 卡片放置在网格上 H 行和 W 方格列。

的 i第一张卡有一个整数 上面写着 A_i ,然后将其放在 R_i从顶部开始的第行和 C_i左起第 列。

多张卡牌可以放置在同一个方格上。

您将首先从每行中拿起最多一张牌。

然后,你将从每列中最多拿起一张牌。

找出所挑选的卡片上所写的整数的最大可能总和。

约束

  • 所有值均为整数。
  • 1 \leq N \leq 10^5
  • 1 \leq H, W \leq 10^5
  • 1 \leq A_i \leq 10^5
  • 1 \leq R_i \leq H
  • 1 \leq C_i \leq W

输入

输入由标准输入按以下格式给出:

N H W
R_1 C_1 A_1
R_2 C_2 A_2
\vdots
R_N C_N A_N

输出

打印所选卡片上所写整数的最大可能总和。


示例输入 1

6 2 2
2 2 2
1 1 8
1 1 5
1 2 9
1 2 7
2 1 4

示例输出 1

28

所挑选的卡片上写的整数之和将为 28,可能的最大值,如果您按如下方式拿起卡片:

  • 拿起第一行的第四张牌。
  • 拿起第二排的第六张牌。
  • 从第一列中拿起第二张卡片。
  • 拿起第二列中的第五张牌。

示例输入 2

13 5 6
1 3 35902
4 6 19698
4 6 73389
3 6 3031
3 1 4771
1 4 4784
2 1 36357
2 1 24830
5 6 50219
4 6 22645
1 2 30739
1 4 68417
1 5 78537

示例输出 2

430590

示例输入 3

1 100000 100000
1 1 1

示例输出 3

1