问题 C: zz请客

内存限制:256 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:271 通过:66

题目描述

        zz工作后,领到了第一份薪水,他想邀请好友庆祝一下。他有 n 个好朋友,每个好朋友有一定的工资 mi 和 友谊值si 。没人想觉得自己穷,所以 zz 邀请的朋友中两两工资差小于 d。现在给出朋友的信息,请求出zz邀请的朋友的最大友谊和是多少。

输入格式

输入的第一行包含两个空格分隔的整数,n和d((1≤n≤105, 1≤d109 ) ——分别是zz的朋友数量和令人感到贫穷的最小金额差。
接下来的n行包含对Kefa的朋友的描述,第(i+1)行包含对第i个朋友的mi,si的描述(0≤mi, si≤109) − 钱的数量和友谊值。


输出格式

输出可达到的最大总友谊值。
示例
Examples
Input1
4 5
75 5
0 100
150 20
75 1
Output1
100
Input2
5 100
0 7
11 32
99 10
46 8
87 54
Output2
111

在第一个样本测试中,最有效的策略是仅由第二个朋友组建伴侣。

在第二个样本测试中,我们可以带走所有的朋友。


输入样例 复制

4 5
75 5
0 100
150 20
75 1

输出样例 复制

100

数据范围与提示



分类标签