题目描述

强哥的甜品店最近推出了 $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$ 是偶数。