比赛场次 127
比赛名称 20120413
比赛状态 已结束比赛成绩
开始时间 2012-04-13 19:00:00
结束时间 2012-04-13 22:00:00
开放分组 全部用户
注释介绍
题目名称 工作进度
输入输出 joba.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 12 简单对比
用户 结果 时间 内存 得分
GravatarTBK AAAAAAAAAAAA 0.000 s 0.00 MiB 100
Gravatar201101 AAAAAAAAAAAA 0.000 s 0.00 MiB 100
GravatarMakazeu AAAAAAAAAAAA 0.000 s 0.00 MiB 100
Gravatar苏轼 AWWWWWWAWAWA 0.000 s 0.00 MiB 33
GravatarOo湼鞶oO AAEEEEEEEEEA 0.000 s 0.00 MiB 25
Gravatarwo shi 刘畅 AWWWWWWWWTWA 0.000 s 0.00 MiB 16
GravatarQhelDIV MMMMMMMMMMMM 0.000 s 0.00 MiB 0

工作进度

★   输入文件:joba.in   输出文件:joba.out   简单对比
时间限制:1 s   内存限制:128 MiB

农夫约翰总是有干不完的活!为了使牧场更高效地运转,他必须要从他的这些工作中牟利才行。他的每一个工作都只占用一个单位的时间。

他的工作日从时间0开始,一共有1,000,000,000 个单位的时间。他当前可以从N(1 <= N <= 100,000)个工作中任选一个,这N个工作编号为1~N。由于在每个单位时间内他只能做一个工作,每项工作有一个时间期限,所以他可能无法完成所有的N项工作。

第i项工作的时间期限为D_i(1 <= D_i <= 1,000,000,000),如果他在这个时间期限之前完成的话,可以获得P_i(1 <= P_i <= 1,000,000,000)的收益。

给定一个工作列表,包括时间期限,请确定约翰能获得的最大收益。注意:答案可能无法用一个32位二进制整数表示。

输入格式:
第1行,一个整数N;
第2~N+1行,第i+1行有两个空格隔开的整数:D_i,P_i;

输出格式:
一行,一个数,即FJ能获得的最大收益。

输入输出样例:
joba.in
3
2 10
1 5
1 7

joba.out
17

输出样例解释:
先在时间1完成3号工作,再在时间2完成1号工作,最大收益为7+10=17。