Div. 1 & Div. 2AI (CI翻译)
Problem Statement
Snuke is choosing problems to use in programming contests he is hosting. Snuke has $N$ problem candidates numbered $1$ to $N$, where problem candidate $i$ has difficulty $i$, genre $K_i$, and interest $A_i$.
Hoping to entertain participants of a wider range of skill levels, he plans to simultaneously hold two contests called Div. 1 and Div. 2, each featuring four problems chosen from the $N$ problem candidates with pairwise distinct genres. However, to conserve problem candidates, the two easier problems in Div. 1 and the two harder problems in Div. 2 will be the same, so only six problems in total will be used.
More formally, the following holds:
- Snuke chooses six problem candidates from the
$N$candidates. Let the numbers of the chosen problem candidates in ascending order be$i_1, i_2, \dots, i_6$. - Problem candidates
$i_1, i_2, i_3, i_4$are used in Div. 2, and they must be of pairwise distinct genres. That is,$K_{i_1}, K_{i_2}, K_{i_3}, K_{i_4}$must be pairwise distinct. - Problem candidates
$i_3, i_4, i_5, i_6$are used in Div. 1, and they must be of pairwise distinct genres. That is,$K_{i_3}, K_{i_4}, K_{i_5}, K_{i_6}$must be pairwise distinct.
Determine whether there exists a valid choice of six problems satisfying the conditions, and if so, find the maximum total interest of the six chosen problems.
Constraints
$6 \leq N \leq 10^5$$1 \leq K_i \leq N$$1 \leq A_i \leq 10^9$- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
K_1 A_1
K_2 A_2
\vdots
K_N A_NOutput
If there exists a valid choice of six problems satisfying the conditions, output the maximum total interest of the six chosen problems; otherwise, output -1.
{"titleZh":"第一组与第二组","bodyZh":"## 题目描述\n\nSnuke 正在为自己举办的编程竞赛挑选题目。Snuke 有 $N$ 个候选题目，编号为 $1$ 到 $N$，其中候选题目 $i$ 的难度为 $i$，类型为 $K_i$，趣味度为 $A_i$。\n\n为了让更广泛技能水平的参赛者都能享受比赛，他计划同时举办名为 Div. 1 和 Div. 2 的两场比赛，每场比赛从 $N$ 个候选题目中选择四道题目，且每场比赛中的题目类型必须两两不同。然而，为了节省候选题目，Div. 1 中较简单的两道题和 Div. 2 中较难的两道题将使用相同的题目，因此总共只会使用六道题。\n\n更正式地说，需要满足以下条件：\n\n- Snuke 从 $N$ 个候选题目中选择六道题目。设所选候选题目的编号按升序排列为 $i_1, i_2, \dots, i_6$。\n- 候选题目 $i_1, i_2, i_3, i_4$ 将用于 Div. 2，且它们的类型必须两两不同。也就是说，$K_{i_1}, K_{i_2}, K_{i_3}, K_{i_4}$ 必须两两不同。\n- 候选题目 $i_3, i_4, i_5, i_6$ 将用于 Div. 1，且它们的类型必须两两不同。也就是说，$K_{i_3}, K_{i_4}, K_{i_5}, K_{i_6}$ 必须两两不同。\n\n请判断是否存在满足条件的六道题目的选择方案；如果存在，求所选六道题目的趣味度总和的最大值。\n\n## 约束条件\n\n- $6 \\leq N \\leq 10^5$\n- $1 \\leq K_i \\leq N$\n- $1 \\leq A_i \\leq 10^9$\n- 所有输入值均为整数。\n\n## 输入格式\n\n输入内容从标准输入中按以下格式给出：\n\n``\nN\nK_1 A_1\nK_2 A_2\n\\vdots\nK_N A_N\n\n\n## 输出格式\n\n如果存在满足条件的六道题目的选择方案，输出所选六道题目的趣味度总和的最大值；否则，输出 -1
样例
8
1 9
3 4
2 3
1 5
4 6
3 3
4 1
5 7
32
7
1 1
2 1
1 1
3 1
4 1
2 1
3 1
-1
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
3971
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。