Schedule
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
读写要求
本题采用文件读写,请在提交代码时使用正确的文件名,否则会导致 RE。
输入文件:schedule.in
输出文件:schedule.out
题目描述
农夫约翰有很多工作要做!为了高效地经营农场,他必须从他所做的每一项工作中赚取利润,每项工作只需要一个时间单位。
他的工作日从时间 开始,总共有 个时间单位。他目前可以从 项工作中选择要做的工作,这些工作被方便地编号为 到 。
虽然理论上他有可能完成所有 项工作,但实际上这是极不可能的,因为他在任何一个时间单位内只能完成一项工作,而截止日期通常会导致他无法完成所有任务。
第 项工作的截止时间为 。如果他在截止时间前完成第 项工作(如果当前时间为 ,那么仅当 的时候他能做这个任务,完成后 ),他将获得 的利润。
给定一系列工作和截止日期,FJ 能够获得的最大总利润是多少?答案可能无法容纳在 位整数中。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 。
输出格式
输出一个整数,表示最大总利润。
数据范围
,。
输入输出样例
3
2 10
1 5
1 7
17
说明
在时间 完成工作 (),在时间 完成工作 ()以最大化收益,最后收益为 。