The problem asks us to find the maximum weight matching in a large graph. From the general theory of matching, we can apply the following greedy method:

• Maintain a set of vertices \(s\). Look at the vertices one by one in descending order of value. When looking at vertex \(v\), if \(v\) can be added to \(s\), add it. Whether it can be added or not is determined by whether there is a matching that covers all vertices contained in \(s\).

Since the graph is large, we need to optimize the determination.

First, consider \(i\) that satisfies \(V_i > L/2\).

This is a bipartite matching problem. For convenience, let’s call a gem with \(V_i \leq L/2\) a small gem, and a gem with \(V_i > L/2\) a large gem. Also, for large gems, let’s set \(W_i=L-V_i\). Matching \((i,j)\) is possible if \(C_i \neq C_j\) and \(V_i \leq W_j\).

It is easier to determine the existence of a matching by considering it in the form of a mincut.

By sorting \(V_i,W_j\) and looking them in ascending order of value, we can find the size of the maximum matching and the set of vertices used in it.

First, let’s explain how to find the size of the matching. Focusing on the form of the mincut, there should be some color \(c\) and a value interval \([l,r)\) such that:

• We cut all small gems in \([0,l)\).
• We cut all gems in \([l,r)\) whose colors are not \(c\).
• We cut all large gems in \([r,-)\).

For each color \(c\), find the minimum cut involving \(c\) to get the overall minimum cut. Also, as mentioned above, this calculation can be done by processing the gems in ascending order of \(V_i,W_j\). Under this assumption, the maximum matching can be found for all prefixes of the gems. If the maximum matching increases when \(W_j\) is added, it is found that \(W_j\) can be used in the optimal solution for the original problem. This is equivalent to performing the greedy method explained at the beginning.

In this way, for every gem with \(V_i>L/2\), it has been determined whether or not to use it in the end. From now on, we will ignore all the gems that are found to be unused. In other words, when we say “a large gem”, we will definitely use it.

Next, consider how to use small gems. Let \(A\) and \(B\) the numbers of small and large gems, respectively.

There is some degree of freedom in matching small gems with large gems. For each color \(c\), the number of small gems of color \(c\) not used in matching with large gems will be important. Let \(f(c)\) be the minimum value of this count. \(f(c)\) itself can be easily found. It is the number of unused gems when making a matching with only small gems of color \(c\) and large gems. (By adding here the small gems of colors other than \(c\) and then appropriately rearranging the matching, all large gems can be matched without changing the number of gems of color \(c\) used.)

Let’s separately consider the case there is a color \(c\) such that \(2f(c)>A-B\), and the case there is not.

If there is a color \(c\) such that \(2f(c)>A-B\):

Obviously, color \(c\) is surplus, and \(2f(c)-(A-B)\) gems need to be eliminated. Conversely, it can be seen from the following discussion that it is sufficient to eliminate only this many. The optimal solution can be obtained by eliminating \(2f(c)-(A-B)\) gems that reduce the value of \(f(c)\) in ascending order of value. Considering how \(f(c)\) is calculated, what is important is the cumulative sums where \(+1\) corresponds to small gems of color \(c\) and \(-1\) corresponds to large gems of colors other than \(c\). We should eliminate small gems of color \(c\) so that the min of these cumulative sums does not change.

If there is no color \(c\) such that \(2f(c)>A-B\):

When \((A-B)\) is even, a perfect matching exists. First, construct a matching that uses all large gems arbitrarily. Here, \((A-B)\) small gems remain. It would be nice if there was no color \(c\) that occupied more than half of them. Suppose there was such a color \(c\). By the way, \(f(c) \leq (A-B)/2\). Take the XOR with the matching that achieves this \(f(c)\), and keep swapping the matching on alternating paths. Then, there is a timing when there are exactly \((A-B)/2\) gems of color \(c\) remaining, and at this point all the remaining gems can be matched.

When \((A-B)\) is odd: We need to eliminate one vertex, and it is enough to eliminate one vertex. We should eliminate the gem with the smallest value while not destroying the matching with large gems. This can be done by finding the matching of small gems and large gems in descending order of \(V_i,W_i\). This yields a matching that uses as valuable small gems as possible. We should eliminate the gem with the smallest value among the gems not used in this matching.

Everything except sorting can be done in linear time, resulting in a solution that runs in \(O(N \log N)\) time in total.

Sample Implementation