2592. 传奇打工王

1000ms 512MB 简单
题目描述
农夫约翰有很多工作要做!为了高效地经营农场,他必须从他所做的每一项工作中赚取利润,每项工作只需要一个时间单位。 他的工作日从时间 $0$ 开始,总共有 $10^9$ 个时间单位。他目前可以从 $N$ ($1 \leq N \leq 10^5$) 项工作中选择要做的工作,这些工作被方便地编号为 $1$ 到 $N$。 虽然理论上他有可能完成所有 $N$ 项工作,但实际上这是极不可能的,因为他在任何一个时间单位内只能完成一项工作,而截止日期通常会导致他无法完成所有任务。 第 $i$ 项工作的截止时间为 $D_i$ ($1 \leq D_i \leq 10^9$)。如果他在截止时间前完成第 $i$ 项工作(如果当前时间为 $t$,那么仅当 $D_i > t$ 的时候他能做这个任务,完成后 $t \rightarrow t+1$,他将获得 $P_i$ ($1 \leq P_i \leq 10^9$) 的利润。 给定一系列工作和截止日期,FJ 能够获得的最大总利润是多少?答案可能无法用 $32$ 位整数存储。
输入格式
第一行输入一个整数 $N$,意义见题目描述。 第二行到第 $N+1$ 行:第 $i+1$ 行包含两个用空格分隔的整数:$D_i$ 和 $P_i$。
输出格式
只有一个数字,表示 FJ 能够获得的最大利润。
样例 1
输入 (Input)

                    
输出 (Output)

                    
在时间 $1$ 完成工作 $3$ $\left(1,7\right)$,在时间 $2$ 完成工作 $1$ $\left(2,10\right)$ 以最大化收益,最后收益为 $7+10=17$。
自测终端 stdin → stdout
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout

                
错误 stderr

                
CtrlEnter提交
自动保存已开启
操作成功
wzs_oj@kernel:~ — wzs-sh
guest@wzsoj:~$
刷新页面 F5
复制 Ctrl+C
粘贴 Ctrl+V
搜索题目
训练中心
站点公告
今日神谕
CSP 倒计时
排行榜
我的提交
Esc 关闭 Enter 跳转 支持模糊匹配数字