← 返回题目列表

AtCoder · abc447_g

G. 分区。 1 & 分区。 2

中文机器翻译题面 查看原题

分数: 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