冰淇淋的风味

题目描述

我们有 $N$ 杯冰淇淋。

第 $i$ 杯冰淇淋的风味为 $F_i$,美味度为 $S_i$($S_i$ 是偶数)。

你将从中选择并吃掉 $2$ 杯。

你的满足感定义如下。

设吃掉的 $2$ 杯冰淇淋的美味度分别为 $s$ 和 $t$($s \ge t$)。

如果这 $2$ 杯风味不同,满足感为 $\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

考虑吃掉第 $2$ 杯和第 $4$ 杯。

第 $2$ 杯的风味为 $2$,美味度为 $10$。

第 $4$ 杯的风味为 $3$,美味度为 $6$。

因为风味不同,满足感为 $10+6=16$。

因此,可以达到满足感 $16$。

无法达到大于 $16$ 的满足感。

4
4 10
3 2
2 4
4 12

17

考虑吃掉第 $1$ 杯和第 $4$ 杯。

第 $1$ 杯的风味为 $4$,美味度为 $10$。

第 $4$ 杯的风味为 $4$,美味度为 $12$。

因为风味相同,满足感为 $12+\frac{10}{2}=17$。

因此,可以达到满足感 $17$。

无法达到大于 $17$ 的满足感。

数据范围

• 输入中的所有值均为整数。
• $2 \le N \le 3 \times 10^5$
• $1 \le F_i \le N$
• $2 \le S_i \le 10^9$
• $S_i$ 是偶数。