工作安排
时间限制:1秒 内存限制:256M
【题目描述】
为了让农场高效运转,他必须靠他的工作赚钱,每项工作花一个单位时间。 他的工作日从 0 时刻开始,有 \(10^9\) 个单位时间。在任一时刻,他都可以选择编号为 1 到 \(N\) 的 \(N\) 项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作,而每项工作又有一个截止日期,所以他很难有时间完成所有 \(N\) 个工作,虽然还是有可能。
对于第 \(i\) 项工作,有个截止时间 \(D_i (1 ≤ D_i ≤ 10^9)\),如果他可以完成这个工作,那么他可以获利 \(P_i(1≤P_i≤10^9)\)。 在给定的工作利润和截止时间下,FJ能够获得的利润最大为多少呢?答案可能会超过 32 位整型。
【输入格式】
第一行是一个整数 \(N\)。
第 \(2\sim N+1\) 行:第 \(i+1\) 行有两个用空格分开的整数:\(D_i\) 和 \(P_i\)。
【输出格式】
输出一行,里面有一个整数,表示最大获利值。
【输入输出样例】
Input
3
2 10
1 5
1 7
Output
17
【数据限制】
对于 \(100\%\) 的数据,\(1≤N≤100000\)。
【来源】
Mr.he