102476: [AtCoder]ABC247 G - Dream Team

Problem Statement

There are $N$ competitive programmers.
The $i$-th competitive programmer belongs to University $A_i$, is good at Subject $B_i$, and has a power of $C_i$.

Consider a team consisting of some of the $N$ people. Let us call such a team a dream team if both of the following conditions are satisfied:

• Any two people belonging to the team belong to different universities.
• Any two people belonging to the team are good at different subjects.

Let $k$ be the maximum possible number of members of a dream team. For each $i=1,2,\ldots,k$, solve the following question.

Question: find the maximum sum of power of people belonging to a dream team consisting of $i$ people.

Constraints

• $1 \leq N \leq 3\times 10^4$
• $1 \leq A_i,B_i \leq 150$
• $1 \leq C_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Let $k$ be the maximum possible number of members of a dream team.
Print $k$ in the first line. Then, print $k$ more lines, each containing the answer to the question for $i=1,2,\ldots,k$, in this order.

Sample Input 1

3
1 1 100
1 20 10
2 1 1

Sample Output 1

2
100
11

• The sum of power of members of a dream team consisting of exactly $1$ person is $100$, when the team consists of the $1$-st competitive programmer.
• The sum of power of members of a dream team consisting of exactly $2$ people is $11$, when the team consists of the $2$-nd and the $3$-rd competitive programmers.
• It is impossible to form a dream team consisting of exactly $3$ people.

Sample Input 2

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

Sample Output 2

4
961524227
1537802822
2032700249
2353208324

问题描述

有N名竞技程序员。

第i名竞技程序员来自大学A_i，擅长科目B_i，并且具有C_i的能力值。

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

• 属于团队的任何两个人都来自不同的大学。
• 属于团队的任何两个人都擅长不同的科目。

设k为梦之队的最大可能人数。 对于每个i=1,2,…,k，解决以下问题。

问题：找到由i个人组成的梦之队中人们的能力值之和的最大值。

约束条件

• 1≤N≤3×10⁴
• 1≤A_i,B_i≤150
• 1≤C_i≤10⁹
• 输入中的所有值都是整数。

输入

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

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

输出

设k为梦之队的最大可能人数。

在第一行打印k。 然后，按照这个顺序打印k行，每行包含对于i=1,2,…,k，问题的答案。

样例输入1

3
1 1 100
1 20 10
2 1 1

样例输出1

2
100
11

• 当团队由第1名竞技程序员组成时，恰好由1人组成的梦之队中成员的能力值之和为100。
• 当团队由第2名和第3名竞技程序员组成时，恰好由2人组成的梦之队中成员的能力值之和为11。
• 不可能恰好由3人组成梦之队。

样例输入2

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

样例输出2

4
961524227
1537802822
2032700249
2353208324