题目描述

夏日炎炎，你来到了一家备受推崇的手工冰淇淋店"甜蜜工坊"。店内展示柜中整齐排列着 $N$ 杯精心制作的冰淇淋，每一杯都是甜品大师的匠心之作。

每杯冰淇淋都有两个关键属性：

• 口味编号：第 $i$ 杯冰淇淋的口味为 $F_i$，不同编号代表不同风味
• 美味指数：第 $i$ 杯冰淇淋的美味度为 $S_i$（保证 $S_i$ 是偶数），数值越高代表口感越佳

作为美食鉴赏家，你决定挑选两杯冰淇淋组成完美搭配。根据冰淇淋店的特殊评分规则，你的满足度将这样计算：

设你选择的两杯冰淇淋的美味度分别为 $s$ 和 $t$，且 $s \geq t$：

• 若两杯冰淇淋口味不同，满足度为两者美味度之和：$s + t$
• 若两杯冰淇淋口味相同，满足度为较高美味度加上较低美味度的一半：$s + \dfrac{t}{2}$

现在，请你找出所有可能的双杯组合中，能够获得的最大满足度，体验极致的美味享受！

输入格式

第一行包含两个整数 $N$ ，分别表示冰淇淋个数。

接下来 $N$ 行，每行描述一个冰淇淋$(F_i,S_i)$表示第 $i$ 个冰淇淋的属性。

输出格式

输出一个整数，表示可以达到的最大满足度。

输入输出样例

输入样例 1

4
4 10
3 2
2 4
4 12

输出样例 1

17

解释

• 选择第1杯（口味4，美味度10）和第4杯（口味4，美味度12）
• 两者口味相同，满足度 = $12 + \dfrac{10}{2} = 12 + 5 = 17$
• 这是所有组合中的最大值

数据范围

对于60%的数据满足：

• $N \leq 1000$

对于100%的数据满足：

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