Logo HelloWorld信息学奥赛题库

少儿编程

时间限制:1 s 空间限制:512 MB

#1790. 孙悟空的奖励

统计

题目描述

在西游记故事中,孙悟空需要对N(1 <= N <= 10,000)个猴子进行教导,每个猴子只需要1个单位的时间。
但是,有些猴子会因为等待时间太长而拒绝接受教导。具体来说,第i只猴子能够接受教导的前提是在时间截止点d_i(1 <= d_i <= 10,000)之前,否则他将不再接受教导。教导每只猴子可以让孙悟空获得g_i的奖励 (1 <= g_i <= 1000)。时间从t=0开始计算,因此在时间t=x时,最多有x只猴子可以接受教导。
请帮助孙悟空确定如果他以最佳方式进行教导,他可以获得的最大奖励。

输入格式:

第1行: N
第2到1+N行: 每行两个值,分别表示每只猴子能够接受教导的奖励 g_i 和 截止时间 d_i。

输出格式:

1个数, 最大的奖励量。

输入样例#1:

4 
10 3 
7 5 
8 1 
2 1 

输出样例#1:

25