UOJ Logo

NOI.AC

1S 512MB

#335. 工作调度

统计

Description

$Farmer John $有太多的工作要做啊! 为了让农场高效运转,他必须靠他的工作赚钱,每项工作花一个单位时间。 他的工作日从$0$时刻开始,有$1000000000$个单位时间(!)。在任一时刻,他都可以选择编号$1 \sim N$的$N(1 <= N <= 100000)$项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作,而每项工作又有一个截止日期,所以他很难有时间完成所有$N$个工作,虽然还是有可能。

对于第$i$个工作,有一个截止时间$D_i(1 <= D_i <= 1000000000)$,如果他可以完成这个工作,那么他可以获利$P_i( 1<=P_i<=1000000000 )$. 在给定的工作利润和截止时间下,$FJ$能够获得的利润最大为多少呢?答案可能会超过$32$位整型。

Input

第$1$行:一个整数$N$. 第$2 \sim N+1$行:第$i+1$行有两个用空格分开的整数:$D_i$和$P_i$.

Output

输出一行,里面有一个整数,表示最大获利值。

Sample Input

3
2 10
1 5
1 7

Sample Output

17

HINT

第$1$个单位时间完成第$3$个工作$(1,7)$,然后在第$2$个单位时间完成第$1$个工作$(2,10)$以达到最大利润