分数: 625 点
问题陈述
Snuke 正在选择要在他主持的编程竞赛中使用的问题。 斯努克有 N 问题候选编号 1 to N,其中问题候选者 i 有 难度 i, 类型 K_i,和 兴趣 A_i.
为了招待更广泛技能水平的参与者,他计划同时举办两场名为“ 分区。 1 和 分区。 2,每个都有四个问题,选自 N 问题候选人 成对不同的流派。 然而,为了保留问题候选者,Div 中的两个更容易的问题。 1 和 Div.1 中的两个更难的问题。 2 是相同的,因此总共只使用 6 个问题。
更正式地说,以下内容成立:
- Snuke 从以下问题中选择六个候选问题 N 候选人。令所选问题候选者的数量按升序排列为 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 \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
没有有效选择满足条件的六个问题。
示例输入 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