育华选购

题目描述

育华食堂推出多款甜品，一共有 $N$ 份甜品。 第 $i$ 份甜品的品类为 $F_i$，美味值为 $S_i$（保证 $S_i$ 为偶数）。

你准备从中挑选两份甜品品尝。总满意度计算规则如下： 设两份甜品的美味值为 $(s,t)$，满足 $s \ge t$。

• 如果两份甜品品类不一样：总满意度 = $s + t$
• 如果两份甜品品类一样：总满意度 = $s + \dfrac{t}{2}$

请求出能够得到的最大总满意度。

输入格式

第一行一个整数 $N$。 接下来 $N$ 行，每行两个整数 $F_i,S_i$。

N
F_1 S_1
F_2 S_2
...
F_N S_N

输出格式

输出最大总满意度。

样例输入 #1

4
1 4
2 10
2 8
3 6

样例输出 #1

16

样例输入 #2

4
4 10
3 2
2 4
4 12

样例输出 #2

17

样例解释

样例1：选择第2份（品类2，美味10）与第4份（品类3，美味6），品类不同，总满意度 $(10+6=16)$，这是最优答案。 样例2：选择第1份、第4份，两份同为品类4，美味值 $(12,10)$，总满意度 $12+\dfrac{10}{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$ 保证是偶数。