问题 D:充电桩的收益
文件提交:无需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$ 元