1879:充电桩的收益

文件提交:无需freopen 内存限制:128 MB 时间限制:1.000 S
评测方式:普通裁判 命题人:
提交:3 解决:2

题目描述

蒜头君在小区里安装了一个电动汽车充电桩,将自家的充电桩的空闲时间开放给其他电动汽车用户付费使用。这种共享充电模式充分提高闲置充电桩的利用率,既可以让蒜头君获得收益,也缓解了其他车主的充电焦虑。现在共有 $n$ 个使用充电桩的申请,编号从 $0$ 到 $n-1$。蒜头君将按编号顺序依次处理所有申请,每个申请 $Q_i (0\le i\le n-1)$ 信息包含两个正整数 $a_i$ 和 $b_i$。

对于申请 $Q_i$ 蒜头君有两种处理策略:

1、接受申请 $Q_i$,将获得 $a_i$ 元收益,但必须放弃接下来的 $b_i$ 个申请。

2、拒绝申请 $Q_i$,没有收益,继续处理下一个申请。

请帮助蒜头君计算出共享充电桩能获得的最大收益。

输入

共 $n+1$ 行,第一行一个整数 $n$,表示使用充电桩的申请数量。接下来 $n$ 行,第 $i$ 行包含两个正整数 $a_i$ 和 $b_i$。表示接受申请 $Q_i$,将获得 $a_i$ 元收益,但必须放弃接下来的 $b_i$ 个申请。

$1\le n\le 10^5, 1\le a_i,b_i\le 10^5$

输出

一行,一个正整数,表示蒜头君共享充电桩获得的最大收益。

样例输入-1 复制

4
3 2
5 4
4 4
3 5

样例输出-1 复制

6

提示

样例解释:蒜头君共收到 $4$ 个使用充电桩的申请,最佳策略为接受申请 $0$ 和申请 $3$。

1、接受申请 $0$,获得 $3$ 元收益,但接下来 $2$ 个申请都必须拒绝。

2、接受申请 $3$,获得 $3$ 元收益。

总收效为 $3+3=6$ 元