Maximizing Gallery Beauty

You are given N paintings. Each painting has a beauty value and an associated artist ID. The art gallery curator wants to display these paintings in an order such that in every group of three consecutive paintings, they are not all by the same artist.

The objective is to reorder the paintings in order to achieve the maximum possible sum of the beauty values while fulfilling the condition that for any three adjacent paintings, at least one painting is by a different artist from the other two. If no such arrangement is possible, output Not possible.

Formally, if the arranged sequence of paintings is represented as an array A where each element is a pair \((b, a)\) with b being the beauty value and a the artist ID, then for every index \(i \ge 2\), it must hold that \(a_{i} \neq a_{i-1}\) or \(a_{i} \neq a_{i-2}\) (i.e. not all three are the same).

Your task is to compute the maximum sum of beauty values that can be achieved under this constraint, or output Not possible if there is no valid arrangement.

inputFormat

The input is read from standard input. The first line contains an integer N indicating the number of paintings. Each of the following N lines contains two integers separated by spaces: the beauty value and the artist ID of a painting.

For example:

6
10 1
20 2
30 1
40 3
50 3
25 2

outputFormat

Output the maximum possible sum of the beauty values if a valid arrangement exists, otherwise output Not possible. The output should be printed to standard output.

## sample

6
10 1
20 2
30 1
40 3
50 3
25 2

175

</p>