{"raw_statement":[{"iden":"problem statement","content":"There are $N$ competitive programmers.  \nThe $i$\\-th competitive programmer belongs to University $A_i$, is good at Subject $B_i$, and has a power of $C_i$.\nConsider 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:\n\n*   Any two people belonging to the team belong to different universities.\n*   Any two people belonging to the team are good at different subjects.\n\nLet $k$ be the maximum possible number of members of a dream team. For each $i=1,2,\\ldots,k$, solve the following question.\nQuestion: find the maximum sum of power of people belonging to a dream team consisting of $i$ people."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 3\\times 10^4$\n*   $1 \\leq A_i,B_i \\leq 150$\n*   $1 \\leq C_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$ $C_1$\n$A_2$ $B_2$ $C_2$\n$\\vdots$\n$A_N$ $B_N$ $C_N$"},{"iden":"sample input 1","content":"3\n1 1 100\n1 20 10\n2 1 1"},{"iden":"sample output 1","content":"2\n100\n11\n\n*   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.\n*   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.\n*   It is impossible to form a dream team consisting of exactly $3$ people."},{"iden":"sample input 2","content":"10\n1 4 142135623\n2 6 457513110\n3 1 622776601\n5 1 961524227\n2 2 360679774\n2 4 494897427\n3 7 416573867\n5 2 915026221\n1 7 320508075\n5 3 851648071"},{"iden":"sample output 2","content":"4\n961524227\n1537802822\n2032700249\n2353208324"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}