现在有 n 项工作,如果你完成了第 i 项工作,你将会在从完成那天开始算起的 Ai 天 时获得 Bi 的工资。
每天你最多只能做一项工作,每项工作也只能做一次,每项工作在当天就能做完。 现在问你在 m 天的时间,能获得的最大工资是多少。
现在有 n 项工作,如果你完成了第 i 项工作,你将会在从完成那天开始算起的 Ai 天 时获得 Bi 的工资。
每天你最多只能做一项工作,每项工作也只能做一次,每项工作在当天就能做完。 现在问你在 m 天的时间,能获得的最大工资是多少。
第一行两个整数n,m
接下来一共n行,每行两个整数ai,bi,第i行的两个整数分别从完成那天开始算起的 Ai 天 时获得 Bi 的工资
样例1
3 4
4 3
4 1
2 2
样例2
5 3
1 2
1 3
1 4
2 1
2 3
样例3
1 1
2 1
样例1
5
样例2
10
样例3
0
【样例 1 解释】
第 1 天做第一项工作,然后在第 4 天拿到 3 工资
第 2 天做第三项工作,然后在第 3 天拿到 2 工作
总共获得 5 工资,这是最大结果。
【数据范围】
数据约束和子任务
对于 100% 的数据,
有 1 ≤ N ≤ 10 ^5
, 1 ≤ M ≤ 10^5
, 1 ≤ Ai ≤ 10^5
, 1 ≤ Bi ≤ 10^4 。