题目描述
在西游记故事中,孙悟空需要对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