分数: 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