E - カードゲーム 3 (Card Game 3) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

JOI 君は,カードゲームで遊んでいる.このカードゲームでより多くの得点を得ることが JOI 君の目標である.

このゲームでは,はじめに N 枚の色付きのカードを受け取る.それぞれのカードには 1 から N までの番号が付けられており,カード i (1 \leqq i \leqq N) には整数 A_{i} が書かれている.また,カードの色は 1 以上 N 以下の整数として表され,カード i の色は C_{i} である.

ゲームを開始する時点での得点は 0 ポイントである.その後,次の操作を 0 回以上繰り返すことで得点を得る.

  • 色の異なる 2 枚のカード i, j を選び,A_{i} + A_{j} ポイントを得点に加算する.選んだカードのうち 1 枚を選んで捨てる.捨てたカードは,それ以降の操作において選ぶことができない.

JOI 君が受け取るカードに関する情報が与えられたとき,JOI 君の最終的な得点としてありうる最大値を求めるプログラムを作成せよ.

入力

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

N
A_{1} C_{1}
A_{2} C_{2}
\vdots
A_{N} C_{N}

出力

標準出力に,JOI 君の最終的な得点としてありうる最大値を表す整数を 1 行で出力せよ.

制約

  • 2 \leqq N \leqq 500\,000.
  • -10^{9} \leqq A_{i} \leqq 10^{9} (1 \leqq i \leqq N).
  • 1 \leqq C_{i} \leqq N (1 \leqq i \leqq N).
  • 入力される値はすべて整数である.

小課題

  1. (13 点) C_{1} = 1,C_{i} = 2 (2 \leqq i \leqq N).
  2. (22 点) N \geqq 3,C_{1} = 1,C_{2} = 1,C_{i} = 2 (3 \leqq i \leqq N),A_{i} \geqq 0 (1 \leqq i \leqq N).
  3. (10 点) N \geqq 3,C_{1} = 1,C_{2} = 1,C_{i} = 2 (3 \leqq i \leqq N).
  4. (28 点) C_{i} \leqq 2 (1 \leqq i \leqq N).
  5. (27 点) 追加の制約はない.

入力例 1

4
5 1
3 2
-1 1
4 2

出力例 1

20

例えば,以下のように 3 回の操作を行うことで最終的な得点を 20 ポイントにすることができる.

はじめ,得点は 0 ポイントである.

1 回目の操作ではカード 1, 2 を選び,8 ポイントを得点に加算する.選んだカードのうち,カード 2 を選んで捨てる.

2 回目の操作ではカード 3, 4 を選び,3 ポイントを得点に加算する.選んだカードのうち,カード 3 を選んで捨てる.

3 回目の操作ではカード 1, 4 を選び,9 ポイントを得点に加算する.選んだカードのうち,カード 1 を選んで捨てる.

最終的な得点を 21 ポイント以上にすることはできないため,20 を出力する.

この入力例は小課題 4, 5 の制約を満たす.

入力例 2

4
3 1
2 2
-5 2
-1 2

出力例 2

7

この入力例は小課題 1, 4, 5 の制約を満たす.

入力例 3

5
3 1
1 1
9 2
2 2
5 2

出力例 3

35

この入力例は小課題 2, 3, 4, 5 の制約を満たす.

入力例 4

8
825766307 4
-97420452 1
675295693 6
662995109 1
-751453145 7
646290641 7
378394053 5
288845388 6

出力例 4

7583311436

この入力例は小課題 5 の制約を満たす.


Source Name

JOIG 2023/2024 春季トレーニング Contest Day2