Flavors

题目描述

我们有 $N$ 个冰淇淋杯。
第 $i$ 个杯子的口味和美味度分别为 $F_i$ 和 $S_i$（$S_i$ 为偶数）。
你将从 $N$ 个杯子中选择并吃掉两个杯子。
这里的满足度定义如下。

设被吃掉的杯子的美味度为 $s$ 和 $t$（$s \ge t$）。 如果两杯的口味不同，你的满足度为 $\displaystyle s+t$。 否则，你的满足度为 $\displaystyle s + \frac{t}{2}$。

求最大可达的满足度。

输入格式

输入按下列格式从标准输入给出： $N$ $F_1$ $S_1$ $F_2$ $S_2$ $\vdots$ $F_N$ $S_N$

输出格式

以整数形式输出答案。

4
1 4
2 10
2 8
3 6

16

4
4 10
3 2
2 4
4 12

17

提示

所有输入值均为整数。 $2 \le N \le 3 \times 10^5$ $1 \le F_i \le N$ $2 \le S_i \le 10^9$ $S_i$ 为偶数。考虑吃第二个和第四个杯子。

第二个杯子的口味是 $2$，美味度是 $10$。 第四个杯子的口味是 $3$，美味度是 $6$。 由于它们的口味不同，你的满足度是 $10+6=16$。

因此，你可以达到满足度 $16$。
你不能达到大于 $16$ 的满足度。
考虑吃第一个和第四个杯子。

第一个杯子的口味是 $4$，美味度是 $10$。 第四个杯子的口味是 $4$，美味度是 $12$。 由于它们的口味相同，你的满足度是 $12+\frac{10}{2}=17$。

因此，你可以达到满足度 $17$。
你不能达到大于 $17$ 的满足度。

标签: AtCoder|abc315C

来源

AtCoder|abc315C