G - Div. 1 & Div. 2 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 625 点

問題文

すぬけくんは、主催するプログラミングコンテストに用いる問題の選定をしています。 すぬけくんは 1 から N までの番号が付けられた N 個の問題案を持っており、問題案 i の 難易度 は i、ジャンル は K_i、面白さ は A_i です。

より幅広い実力の参加者に楽しんでもらいたいすぬけくんは、Div. 1、Div. 2 と呼ばれる 2 つのコンテストの同時開催を企画しており、各コンテストでは ジャンルの相異なる 4 つの問題を N 個の問題案の中から選んで出題します。 ただし、問題案の節約のため、Div. 1 の難易度下位 2 問と Div. 2 の難易度上位 2 問には共通のものを使い、合計で 6 問のみを用いる予定です。

より形式的には以下の通りです。

  • すぬけくんは、N 個の問題案の中から 6 つの問題案を選ぶ。選ぶ問題案の番号を昇順に i_1,i_2,\dots,i_6 とする。
  • 問題案 i_1,i_2,i_3,i_4 が Div. 2 に用いられ、これらは相異なるジャンルのものでなければならない。すなわち、K_{i_1},K_{i_2},K_{i_3},K_{i_4} は相異なる必要がある。
  • 問題案 i_3,i_4,i_5,i_6 が Div. 1 に用いられ、これらは相異なるジャンルのものでなければならない。すなわち、K_{i_3},K_{i_4},K_{i_5},K_{i_6} は相異なる必要がある。

条件を満たすような 6 問の選び方が存在するか判定し、存在する場合は選ぶ 6 問の面白さの総和の最大値を求めてください。

制約

  • 6\leq N \leq 10^5
  • 1\leq K_i \leq N
  • 1\leq A_i \leq 10^9
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
K_1 A_1
K_2 A_2
\vdots
K_N A_N

出力

条件を満たすような 6 問の選び方が存在するならば選ぶ 6 問の面白さの総和の最大値を、存在しないならば -1 を出力せよ。

入力例 1

8
1 9
3 4
2 3
1 5
4 6
3 3
4 1
5 7

出力例 1

32

例として、問題案 1,2,3,5,6,8 を選ぶことを考えます。 このとき、K_{i_1}=1,K_{i_2}=3,K_{i_3}=2,K_{i_4}=4 は相異なり、また K_{i_3}=2,K_{i_4}=4,K_{i_5}=3,K_{i_6}=5 も相異なるため、これは条件を満たす選び方です。 また、このときの面白さの総和は 9+4+3+6+3+7=32 であり、これが最大です。

入力例 2

7
1 1
2 1
1 1
3 1
4 1
2 1
3 1

出力例 2

-1

条件を満たすような 6 問の選び方は存在しません。

入力例 3

16
1 593
3 449
15 991
9 310
1 355
15 68
3 431
15 580
14 757
14 218
14 934
9 328
3 676
3 355
1 221
6 80

出力例 3

3971

Score : 625 points

Problem Statement

Snuke is choosing problems to use in programming contests he is hosting. Snuke has N problem candidates numbered 1 to N, where problem candidate i has difficulty i, genre K_i, and interest A_i.

Hoping to entertain participants of a wider range of skill levels, he plans to simultaneously hold two contests called Div. 1 and Div. 2, each featuring four problems chosen from the N problem candidates with pairwise distinct genres. However, to conserve problem candidates, the two easier problems in Div. 1 and the two harder problems in Div. 2 will be the same, so only six problems in total will be used.

More formally, the following holds:

  • Snuke chooses six problem candidates from the N candidates. Let the numbers of the chosen problem candidates in ascending order be i_1, i_2, \dots, i_6.
  • Problem candidates i_1, i_2, i_3, i_4 are used in Div. 2, and they must be of pairwise distinct genres. That is, K_{i_1}, K_{i_2}, K_{i_3}, K_{i_4} must be pairwise distinct.
  • Problem candidates i_3, i_4, i_5, i_6 are used in Div. 1, and they must be of pairwise distinct genres. That is, K_{i_3}, K_{i_4}, K_{i_5}, K_{i_6} must be pairwise distinct.

Determine whether there exists a valid choice of six problems satisfying the conditions, and if so, find the maximum total interest of the six chosen problems.

Constraints

  • 6 \leq N \leq 10^5
  • 1 \leq K_i \leq N
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
K_1 A_1
K_2 A_2
\vdots
K_N A_N

Output

If there exists a valid choice of six problems satisfying the conditions, output the maximum total interest of the six chosen problems; otherwise, output -1.

Sample Input 1

8
1 9
3 4
2 3
1 5
4 6
3 3
4 1
5 7

Sample Output 1

32

For example, consider choosing problem candidates 1, 2, 3, 5, 6, 8. In this case, K_{i_1}=1, K_{i_2}=3, K_{i_3}=2, K_{i_4}=4 are pairwise distinct, and K_{i_3}=2, K_{i_4}=4, K_{i_5}=3, K_{i_6}=5 are also pairwise distinct, so this is a valid choice. The total interest in this case is 9+4+3+6+3+7=32, which is the maximum.

Sample Input 2

7
1 1
2 1
1 1
3 1
4 1
2 1
3 1

Sample Output 2

-1

There is no valid choice of six problems satisfying the conditions.

Sample Input 3

16
1 593
3 449
15 991
9 310
1 355
15 68
3 431
15 580
14 757
14 218
14 934
9 328
3 676
3 355
1 221
6 80

Sample Output 3

3971