礼物

问题描述

面条老师获得了一系列礼物，每个礼物带有一个数字标签 $a_i$ 和对应价值 $b_i$。
面条老师需要选定一个正整数 $k$，保留所有数字标签介于 $[k-1, k+1]$ 之间的礼物（即标签为 $k-1$、$k$ 或 $k+1$ 的礼物），并最大化所有保留礼物的价值和。

请计算面条老师可以获得的最大礼物价值和。

输入格式

第一行一个正整数 $n$，表示礼物的总数。

接下来 $n$ 行，每行两个整数 $a_i, b_i$，分别表示第 $i$ 个礼物的数字标签和价值。

输出格式

输出一行一个整数，表示面条老师能获得的最大礼物价值和。

样例

输入

5
1 2
3 5
2 1
1 1
5 8

输出

13

样例解释

选择 $k=4$ 时，保留标签在 $[3,5]$ 区间内的礼物：

• 标签为 $3$、价值为 $5$ 的礼物
• 标签为 $5$、价值为 $8$ 的礼物 价值和为 $5+8=13$，为所有选择中的最大值。

数据范围与约定

共10组数据，每组数据点10分。

• 对于50%的数据：$1 \le n, a_i, b_i \le 10$
• 对于100%的数据：$1 \le n, a_i, b_i \le 10^5$