AT_abc315_c [ABC315C] Flavors

[problemUrl]: https://atcoder.jp/contests/abc315/tasks/abc315_c $ N $ カップのアイスクリームがあります。 $ i $ カップ目の味は $ F_i $ 、美味しさは $ S_i $ ( $ S_i $ は偶数 ) です。 あなたは、 $ N $ 個のカップの中から $ 2 $ つを選んで食べることにしました。 このときの満足度は次のように定義されます。 - 食べたアイスクリームの美味しさを $ s,t $ ( 但し、 $ s\ \ge\ t $ ) とする。 - $ 2 $ つのカップの味が異なるなら、満足度は $ \displaystyle\ s+t $ である。 - そうでないなら、満足度は $ \displaystyle\ s\ +\ \frac{t}{2} $ である。 満足度として達成可能な最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ F_1 $ $ S_1 $ $ F_2 $ $ S_2 $ $ \vdots $ $ F_N $ $ S_N $

答えを整数として出力せよ。

### 制約 - 入力は全て整数 - $ 2\ \le\ N\ \le\ 3\ \times\ 10^5 $ - $ 1\ \le\ F_i\ \le\ N $ - $ 2\ \le\ S_i\ \le\ 10^9 $ - $ S_i $ は偶数 ### Sample Explanation 1 $ 2 $ カップ目と $ 4 $ カップ目のアイスを食べることを考えます。 - $ 2 $ カップ目の味は $ 2 $ 、美味しさは $ 10 $ です。 - $ 4 $ カップ目の味は $ 3 $ 、美味しさは $ 6 $ です。 - 両者の味は異なるので、満足度は $ 10+6=16 $ です。 以上より、満足度 $ 16 $ を達成できます。 満足度を $ 16 $ より大きくすることはできません。 ### Sample Explanation 2 $ 1 $ カップ目と $ 4 $ カップ目のアイスを食べることを考えます。 - $ 1 $ カップ目の味は $ 4 $ 、美味しさは $ 10 $ です。 - $ 4 $ カップ目の味は $ 4 $ 、美味しさは $ 12 $ です。 - 両者の味は同じなので、満足度は $ 12+\frac{10}{2}=17 $ です。 以上より、満足度 $ 17 $ を達成できます。 満足度を $ 17 $ より大きくすることはできません。