#1344. [USACO09OPEN] Work Scheduling G

[USACO09OPEN] Work Scheduling G

题目描述

农夫约翰有很多工作要做!为了高效地经营农场,他必须从他所做的每一项工作中赚取利润,每项工作只需要一个时间单位。

他的工作日从时间 00 开始,总共有 10910^9 个时间单位。他目前可以从 NN (1≤N≤1051 \leq N \leq 10^5) 项工作中选择要做的工作,这些工作被方便地编号为 11 到 NN。

虽然理论上他有可能完成所有 NN 项工作,但实际上这是极不可能的,因为他在任何一个时间单位内只能完成一项工作,而截止日期通常会导致他无法完成所有任务。

第 ii 项工作的截止时间为 DiD_i (1≤Di≤1091 \leq D_i \leq 10^9)。如果他在截止时间前完成第 ii 项工作(如果当前时间为 tt,那么仅当 Di>tD_i > t 的时候他能做这个任务,完成后 t→t+1t \rightarrow t+1,他将获得 PiP_i (1≤Pi≤1091 \leq P_i \leq 10^9) 的利润。

给定一系列工作和截止日期,FJ 能够获得的最大总利润是多少?答案可能无法用 3232 位整数存储。

输入格式

第一行输入一个整数 NN,意义见题目描述。

第二行到第 N+1N+1 行:第 i+1i+1 行包含两个用空格分隔的整数:DiD_i 和 PiP_i。

输出格式

只有一个数字,表示 FJ 能够获得的最大利润。

样例

3 
2 10 
1 5 
1 7 
17 

题目来源:洛谷 P2949