{"problem":{"name":"Jewels","description":{"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"nikkei2019_qual_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"nikkei2019_qual_f","tags":[],"sample_group":[["5 2\n1 1\n1 2\n1 3\n2 4\n2 5","\\-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."],["5 2\n1 1\n1 2\n2 3\n2 4\n2 5","\\-1\n9\n12\n12\n15"],["8 4\n3 2\n2 3\n4 5\n1 7\n3 11\n4 13\n1 17\n2 19","\\-1\n24\n-1\n46\n-1\n64\n-1\n77"],["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","\\-1\n145\n173\n285\n318\n398\n431\n491\n524\n576\n609\n634\n653\n666\n678"]],"created_at":"2026-03-03 11:01:14"}}