题目描述

$N$ 人の競技プログラマがいます。
$i$ 人目の競技プログラマは、所属大学が $A_i$、得意分野が $B_i$、強さが $C_i$ です。

$N$ 人のうちの何人かによって構成されるチームであって、次の条件をともに満たすものをドリームチームと呼びます。

• チームに属するどの $2$ 人の所属大学も異なる
• チームに属するどの $2$ 人の得意分野も異なる

構成可能なドリームチームの人数の最大値を $k$ とします。各 $i=1,2,\ldots,k$ について、次の問題を解いてください。

問題：ちょうど $i$ 人で構成されるドリームチームについて、チームに所属する人の強さの合計の最大値を求めてください。

输入格式

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

$N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_N$ $B_N$ $C_N$

输出格式

構成可能なドリームチームの人数の最大値を $k$ とする。
1行目には $k$ を出力し、その後、$k$ 行にわたって、$i=1,2,\ldots,k$ のときの問題に対する答えを順に出力せよ。

题目大意

平面中有 $n$ 个点，坐标为 $(a_i,b_i)$，权值为 $c_i$。

对于每一行每一列最多只能选一个点，最大化选点个数 $k$ 并输出。

对于每个 $i,i=1,2……k$，最大化选出 $i$ 个点的权值和。

3
1 1 100
1 20 10
2 1 1

2
100
11

10
1 4 142135623
2 6 457513110
3 1 622776601
5 1 961524227
2 2 360679774
2 4 494897427
3 7 416573867
5 2 915026221
1 7 320508075
5 3 851648071

4
961524227
1537802822
2032700249
2353208324

提示

制約

• $1\ \leq\ N\ \leq\ 3\times\ 10^4$
• $1\ \leq\ A_i,B_i\ \leq\ 150$
• $1\ \leq\ C_i\ \leq\ 10^9$
• 入力に含まれる値は全て整数である

Sample Explanation 1

- ちょうど $1$ 人で構成されるドリームチームは、$1$ 人目の競技プログラマからなるとき強さの合計が $100$ で最大になります。 - ちょうど $2$ 人で構成されるドリームチームは、$2,3$ 人目の競技プログラマからなるとき強さの合計が $11$ で最大になります。 - ちょうど $3$ 人で構成されるドリームチームを作ることはできません。