G - Dream Team Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

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

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

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

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

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

制約

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

入力

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

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 のときの問題に対する答えを順に出力せよ。

入力例 1

3
1 1 100
1 20 10
2 1 1

出力例 1

2
100
11
  • ちょうど 1 人で構成されるドリームチームは、1 人目の競技プログラマからなるとき強さの合計が 100 で最大になります。
  • ちょうど 2 人で構成されるドリームチームは、2,3 人目の競技プログラマからなるとき強さの合計が 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

Score : 600 points

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