AT_abc315_c [ABC315C] Flavors

题目描述

有 $N$ 杯冰淇淋。
第 $i$ 杯的口味为 $F_i$，美味度为 $S_i$（$S_i$ 是偶数）。

你决定从 $N$ 杯冰淇淋中选出两杯来吃。
此时的满足度定义如下：

• 吃掉的两杯冰淇淋的美味度分别为 $s, t$（其中 $s \ge t$）。
  • 如果两杯的口味不同，则满足度为 $s + t$。
  • 如果两杯的口味相同，则满足度为 $s + \frac{t}{2}$。

请你求出可以达到的最大满足度。

输入格式

输入以如下格式从标准输入给出。

$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$ 是偶数。

样例解释 1

考虑吃第 $2$ 杯和第 $4$ 杯冰淇淋。

• 第 $2$ 杯的口味为 $2$，美味度为 $10$。
• 第 $4$ 杯的口味为 $3$，美味度为 $6$。
• 两者口味不同，所以满足度为 $10+6=16$。 因此，可以达到满足度 $16$。无法得到比 $16$ 更大的满足度。

样例解释 2

考虑吃第 $1$ 杯和第 $4$ 杯冰淇淋。

• 第 $1$ 杯的口味为 $4$，美味度为 $10$。
• 第 $4$ 杯的口味为 $4$，美味度为 $12$。
• 两者口味相同，所以满足度为 $12+\frac{10}{2}=17$。 因此，可以达到满足度 $17$。无法得到比 $17$ 更大的满足度。

由 ChatGPT 4.1 翻译