{"problem":{"name":"Colorful Subsequence","description":{"content":"There are $N$ balls lined up in a row.   The $i$\\-th ball from the left is of color $C_i$ and has a value of $V_i$. Takahashi wants to remove **exactly** $K$ balls from this row so that no two adjacen","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc345_e"},"statements":[{"statement_type":"Markdown","content":"There are $N$ balls lined up in a row.  \nThe $i$\\-th ball from the left is of color $C_i$ and has a value of $V_i$.\nTakahashi wants to remove **exactly** $K$ balls from this row so that no two adjacent balls have the same color when arranging the remaining balls without changing the order. Additionally, under that condition, he wants to maximize the total value of the balls remaining in the row.\nDetermine if Takahashi can remove $K$ balls so that no two adjacent balls in the remaining row have the same color. If it is possible, find the maximum possible total value of the remaining balls.\n\n## Constraints\n\n*   $1\\leq K<N\\leq 2\\times 10^5$\n*   $K\\leq 500$\n*   $1\\leq C_i\\leq N$\n*   $1\\leq V_i\\leq 10^9$\n*   All input values are integers.\n\n## Input\n\nThe 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$\\vdots$\n$C_N$ $V_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc345_e","tags":[],"sample_group":[["5 2\n1 1\n3 5\n3 3\n1 4\n1 2","10\n\nAfter removing the $3$\\-rd and $5$\\-th balls from the left, the remaining balls are of colors $1, 3, 1$ from left to right, so no two adjacent balls have the same color, satisfying the condition.  \nThe total value of the remaining balls is $V_1+V_2+V_4=1+5+4=10$.  \nThere are other ways to remove two balls from the five balls so that no two adjacent balls have the same color, but the total value of the remaining balls is maximized when removing the $3$\\-rd and $5$\\-th balls.\nHence, print $10$."],["3 1\n1 10\n1 10\n1 10","\\-1\n\nNo matter how you remove one ball, balls of color $1$ will end up next to each other.  \nHence, print $-1$."],["3 1\n1 1\n2 2\n3 3","5\n\nNote that exactly $K$ balls must be removed."]],"created_at":"2026-03-03 11:01:14"}}