{"raw_statement":[{"iden":"problem statement","content":"There are $N$ jewels, numbered $1$ to $N$. The color of these jewels are represented by integers between $1$ and $K$ (inclusive), and the color of Jewel $i$ is $C_i$. Also, these jewels have specified values, and the value of Jewel $i$ is $V_i$.\nSnuke would like to choose some of these jewels to exhibit. Here, the set of the chosen jewels must satisfy the following condition:\n\n*   For each chosen jewel, there is at least one more jewel of the same color that is chosen.\n\nFor each integer $x$ such that $1 \\leq x \\leq N$, determine if it is possible to choose exactly $x$ jewels, and if it is possible, find the maximum possible sum of the values of chosen jewels in that case."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq K \\leq \\lfloor N/2 \\rfloor$\n*   $1 \\leq C_i \\leq K$\n*   $1 \\leq V_i \\leq 10^9$\n*   For each of the colors, there are at least two jewels of that color.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$C_1$ $V_1$\n$C_2$ $V_2$\n$:$\n$C_N$ $V_N$"},{"iden":"sample input 1","content":"5 2\n1 1\n1 2\n1 3\n2 4\n2 5"},{"iden":"sample output 1","content":"\\-1\n9\n6\n14\n15\n\nWe cannot choose exactly one jewel.\nWhen choosing exactly two jewels, the total value is maximized when Jewel $4$ and $5$ are chosen.\nWhen choosing exactly three jewels, the total value is maximized when Jewel $1, 2$ and $3$ are chosen.\nWhen choosing exactly four jewels, the total value is maximized when Jewel $2, 3, 4$ and $5$ are chosen.\nWhen choosing exactly five jewels, the total value is maximized when Jewel $1, 2, 3, 4$ and $5$ are chosen."},{"iden":"sample input 2","content":"5 2\n1 1\n1 2\n2 3\n2 4\n2 5"},{"iden":"sample output 2","content":"\\-1\n9\n12\n12\n15"},{"iden":"sample input 3","content":"8 4\n3 2\n2 3\n4 5\n1 7\n3 11\n4 13\n1 17\n2 19"},{"iden":"sample output 3","content":"\\-1\n24\n-1\n46\n-1\n64\n-1\n77"},{"iden":"sample input 4","content":"15 5\n3 87\n1 25\n1 27\n3 58\n2 85\n5 19\n5 39\n1 58\n3 12\n4 13\n5 54\n4 100\n2 33\n5 13\n2 55"},{"iden":"sample output 4","content":"\\-1\n145\n173\n285\n318\n398\n431\n491\n524\n576\n609\n634\n653\n666\n678"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}