梦之队

题目描述

有 $N$ 名竞技编程选手。

第 $i$ 名选手属于大学 $A_i$，擅长科目 $B_i$，能力值为 $C_i$。

考虑由这 $N$ 人中的一些人组成的队伍。如果满足以下两个条件，则称这样的队伍为梦之队：

• 队伍中任意两人属于不同的大学。
• 队伍中任意两人擅长的科目不同。

设 $k$ 为梦之队成员数可能的最大值。对每个 $i=1,2,\ldots,k$，解决下面的问题。

问题：求由恰好 $i$ 人组成的梦之队中，成员能力值之和的最大值。

输入格式

输入按以下格式从标准输入给出：

N
A_1 B_1 C_1
A_2 B_2 C_2
⋮
A_N B_N C_N

输出格式

设 $k$ 为梦之队成员数可能的最大值。

第一行输出 $k$。接下来输出 $k$ 行，第 $i$ 行输出对 $i=1,2,\ldots,k$ 中相应问题的答案，按此顺序。

样例

3
1 1 100
1 20 10
2 1 1

2
100
11

由恰好 1 人组成的梦之队的能力值之和为 100，此时队伍由第 1 名选手组成。

由恰好 2 人组成的梦之队的能力值之和为 11，此时队伍由第 2 名和第 3 名选手组成。

不可能组成恰好由 3 人组成的梦之队。

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$
• 输入中的所有值都是整数。