配点 : $800$ 点

問題文

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

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

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

あなたは各行からそれぞれ $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$

入力

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

$N$ $H$ $W$

$R_1$ $C_1$ $A_1$

$R_2$ $C_2$ $A_2$

$\vdots$

$R_N$ $C_N$ $A_N$

出力

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

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

28

以下のように取ると、取ったカードに書かれた整数の合計は $28$ になり、このときが最大です。

• $1$ 行目から $4$ 番目のカードを取ります。
• $2$ 行目から $6$ 番目のカードを取ります。
• $1$ 列目から $2$ 番目のカードを取ります。
• $2$ 列目から $5$ 番目のカードを取ります。

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