题目描述

$H$ 行 $W$ 列に並んだマス目の上に合計 $N$ 枚のカードが置かれています。

$i$ 番目のカードには整数 $A_i$ が書かれており、上から $R_i$ 行目、左から $C_i$ 列目のマスの上に置かれています。

同じマスに複数枚のカードが置かれていることもあります。

あなたは各行からそれぞれ $1$ 枚までカードを選んで取ります。

次に、各列からそれぞれ $1$ 枚までカードを選んで取ります。

取ったカードに書かれた整数の合計の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

取ったカードに書かれた整数の合計の最大値を出力せよ。

题目大意

有N张卡片放置在一个网格上，其中有H行和W列正方形。

第i张卡片上写有一个整数Ai，它被放置在从顶部开始的第Ri行和从左侧开始的第Ci列的正方形上。

多张牌可以放在同一个正方形上。

您将首先从每行最多拾取一张卡。

然后，您将从每列中最多提取一张卡。

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

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

28

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

430590

1 100000 100000
1 1 1

1

提示

制約

• 入力は全て整数である。
• $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$

Sample Explanation 1

以下のように取ると、取ったカードに書かれた整数の合計は $28$ になり、このときが最大です。 - $1$ 行目から $4$ 番目のカードを取ります。 - $2$ 行目から $6$ 番目のカードを取ります。 - $1$ 列目から $2$ 番目のカードを取ります。 - $2$ 列目から $5$ 番目のカードを取ります。