/ Vijos / 题库 /

工作安排

工作安排

时间限制: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

信息

ID
2169
难度
9
分类
贪心 点击显示
标签
递交数
1
已通过
1
通过率
100%
被复制
7
上传者