You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC315C] Flavors

题面翻译

给定 $n$ 个二元组，每个二元组形如 $(F,S)$，要求选定 $2$ 个二元组，若 $F$ 相等，则贡献为 $S_{1}+\frac{S_{2}}{2}(S_{1} \ge S_{2})$；反之，贡献为 $S_{1}+S_{2}$，最大化贡献。$1 \le n \le 3 \times 10^5$。

题目描述

We have N cups of ice cream. The flavor and deliciousness of the i-th cup are Fi​ and Si​, respectively (Si​ is an even number).

You will choose and eat two of the N cups. Your satisfaction here is defined as follows.

• Let s and t (s≥t) be the deliciousness of the eaten cups.
  • If the two cups have different flavors, your satisfaction is s+t.
  • Otherwise, your satisfaction is s+t/2.

Find the maximum achievable satisfaction.

输入格式

输入格式如下：

$N$ $F_1$ $S_1$ $F_2$ $S_2$ $\vdots$ $F_N$ $S_N$

输出格式

输出一个正整数表示答案。

样例 #1

样例输入 #1

4
1 4
2 10
2 8
3 6

样例输出 #1

16

样例 #2

样例输入 #2

4
4 10
3 2
2 4
4 12

样例输出 #2

17

提示

数据范围

• 输入都是正整数
• $2\ \le\ N\ \le\ 3\ \times\ 10^5$
• $1\ \le\ F_i\ \le\ N$
• $2\ \le\ S_i\ \le\ 10^9$
• $S_i$ 是偶数