约翰有太多的工作要做。为了让农场高效运转,他必须靠他的工作赚钱,每项工作花一个单位时间。 他的工作日从 0 时刻开始,有 10^9 个单位时间。在任一时刻,他都可以选择编号 1 到 N 的 N(1 \leq N \leq 10^5) 项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作,而每项工作又有一个截止日期,所以他很难有时间完成所有N个工作,虽然还是有可能。 对于第 i 个工作,有一个截止时间 D_i(1 \leq D_i \leq 10^9),如果他可以完成这个工作,那么他可以获利 P_i( 1\leq P_i\leq 10^9 ). 在给定的工作利润和截止时间下,约翰能够获得的利润最大为多少.
第一行一个数字N;
第2~N+1行,每行两个数字,D\_i 和 P\_i
一个数字,表示约翰能获得的最大利润!
3 2 10 1 5 1 7
17
完成任务 3 (1,7)在时间 1 然后完成任务1 (2,10),在截至时间2,最后可以赚(7 + 10 -> 17).