AT_abc447_g [ABC447G] Div. 1 & Div. 2

Snuke 准备举办一场编程比赛，他正在为此挑选题目。他手头有 $N$ 道候选题目，编号为 $1$ 到 $N$。其中，编号为 $i$ 的题目**难度**为 $i$，**类型**为 $K_i$，**趣味值**为 $A_i$。 为了吸引不同水平的参赛选手，他计划同时举办 **Div. 1** 和 **Div. 2** 两场比赛。每场比赛都需要从这 $N$ 道备选题目中挑选 4 道，并且这 4 道题的**类型必须两两不同**。此外，为了节省题目，Div. 1 中最简单的两道题将与 Div. 2 中最难的两道题完全相同。因此，两场比赛总共只需使用 6 道不同的题目。 形式化地说： - Snuke 需要从 $N$ 道题目中选出 6 道，设这 6 道题目的编号（即难度）按升序排列为 $i_1, i_2, i_3, i_4, i_5, i_6$。 - Div. 2 采用的题目为 $i_1, i_2, i_3, i_4$，且它们的类型必须互不相同（即 $K_{i_1}, K_{i_2}, K_{i_3}, K_{i_4}$ 两两不同）。 - Div. 1 采用的题目为 $i_3, i_4, i_5, i_6$，且它们的类型必须互不相同（即 $K_{i_3}, K_{i_4}, K_{i_5}, K_{i_6}$ 两两不同）。 请你判断是否存在满足上述条件的选题方案。如果存在，请计算出被选出的 6 道题目的**总趣味值之和的最大值**。

输入来自标准输入，格式如下： > $ N $ > $ K_1 $ $ A_1 $ > $ K_2 $ $ A_2 $ > $ \vdots $ > $ K_N $ $ A_N $

如果存在满足条件的选择方案，输出 6 道题目的总趣味值之和的最大值；否则，输出 `-1`。

### 样例 1 解释 可以选择编号为 $1, 2, 3, 5, 6, 8$ 的这 6 道题目。 在这种方案下： - Div. 2 的题目类型为 $K_{i_1}=1, K_{i_2}=3, K_{i_3}=2, K_{i_4}=4$，两两不同； - Div. 1 的题目类型为 $K_{i_3}=2, K_{i_4}=4, K_{i_5}=3, K_{i_6}=5$，也两两不同。 因此这是一个合法的选题方案。这 6 道题的总趣味值为 $9+4+3+6+3+7=32$，并且这也是能得到的最大值。 ### 样例 2 解释 不存在满足条件的选题方案，因此输出 `-1`。 ### 数据范围 - $6 \leq N \leq 10^5$ - $1 \leq K_i \leq N$ - $1 \leq A_i \leq 10^9$ - 所有输入均为整数。 翻译由 Gemini 3.1 Pro 提供。