AT_abc447_g [ABC447G] Div. 1 & Div. 2

すぬけくんは、主催するプログラミングコンテストに用いる問題の選定をしています。 すぬけくんは $ 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 $ 問の面白さの総和の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ > > $ K_1 $ $ A_1 $ > > $ K_2 $ $ A_2 $ > > $ \vdots $ > > $ K_N $ $ A_N $

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

### Sample Explanation 1 例として、問題案 $ 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 $ であり、これが最大です。 ### Sample Explanation 2 条件を満たすような $ 6 $ 問の選び方は存在しません。 ### Constraints - $ 6\leq N \leq 10^5 $ - $ 1\leq K_i \leq N $ - $ 1\leq A_i \leq 10^9 $ - 入力は全て整数