Problem C
Packing Pests
You are an employee #333-4-591032 at a candy sorting company. Your job is simple. $N$ candies, of $M$ different colors, will be thrown in your direction, one at a time. The $i^\text {th}$ thrown candy will have color $C_ i$ and value $V_ i$. Each time, you must either swat the candy away or catch it and put it into your box.
You must never put two candies of the same color into your box. The moment your box contains candies of all $M$ colors, your box will be closed, packaged and delivered, and a new, empty box will be provided to you. No candies may remain in your box at the end (that is, after the last candy is thrown and the last box potentially shipped.)
Minimize the total value of candies swatted away.
Input
The first line of input contains two integers, $N$ ($1 \leq N \leq 200\, 000$) and $M$ ($1 \leq M \leq N$), the number of candies and the number of different colors of candy, respectively.
The next $N$ lines of input contain the descriptions of the candies. In particular, the $i^\text {th}$ of these lines contains two integers $C_ i$ ($1\leq C_ i \leq M$) and $V_ i$ ($1 \leq V_ i \leq 10^9$), denoting that the $i^\text {th}$ candy will have color $C_ i$ and value $V_ i$.
It is guaranteed that for all positive integers $k < M$, there exists some $j$ such that $C_ j = k$.
Output
Output a single line containing a string with exactly $N$ characters. The $i^\text {th}$ character of this string must be X if the $i^\text {th}$ candy is swatted away, and O if the candy is caught and put into your box.
You must ensure that by following this process, no candies of the same color are ever in your box, no candies remain in your box at the end, and, among all such possible processes following these criteria, the total value of candies swatted away is minimized.
If there are multiple correct answers, you can output any of them.
Sample Input 1 | Sample Output 1 |
---|---|
8 3 1 10 2 40 1 25 3 60 2 15 2 10 3 20 1 5 |
XOOOOXOO |