← 返回题目列表

AtCoder · abc315_c

E. 口味

中文机器翻译题面 查看原题

分数: 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.