分数: 300 点
问题陈述
我们有 N 杯冰淇淋。
的风味和美味 i第杯是 F_i 和 S_i分别 (S_i 是偶数)。
您将选择并吃其中的两个 N 杯子。
您的满意度定义如下。
- 让 s 和 t (s \ge t)是所吃杯子的美味。
- 如果两杯口味不同,您满意的是 \displaystyle s+t.
- 否则,您满意的是 \displaystyle s + \frac{t}{2}.
找到可实现的最大满意度。
约束
- 所有输入值均为整数。
- 2 \le N \le 3 \times 10^5
- 1 \le F_i \le N
- 2 \le S_i \le 10^9
- S_i 是偶数。
输入
输入由标准输入按以下格式给出:
N F_1 S_1 F_2 S_2 \vdots F_N S_N
输出
将答案打印为整数。
示例输入 1
4 1 4 2 10 2 8 3 6
示例输出 1
16
考虑吃第二杯和第四杯。
- 第二杯有味道 2 和美味 10.
- 第四杯有味道 3 和美味 6.
- 由于口味不同,您的满意是 10+6=16.
这样,您就可以达到满意的效果 16.
您无法获得大于 16.
示例输入 2
4 4 10 3 2 2 4 4 12
示例输出 2
17
考虑吃第一杯和第四杯。
- 第一杯有味道 4 和美味 10.
- 第四杯有味道 4 和美味 12.
- 由于味道相同,您满意 12+\frac{10}{2}=17.
这样,您就可以达到满意的效果 17.
您无法获得大于 17.