Kefa 想去餐厅庆祝他的第一份高薪。然而,他需要陪伴。
Kefa有n个朋友,如果Kefa提出要求,每个朋友都会同意去餐厅。每个朋友的特征是他拥有的金钱数量以及与 Kefa 的友谊因素。鹦鹉不希望任何朋友与公司中的其他人相比感到贫穷(Kefa 不算在内)。如果公司里有人比他多至少 d 个单位的钱,一个朋友就会感觉很穷。另外,科发希望公司成员的总友谊系数最大。帮他邀请一个最合适的公司!
输入
输入的第一行包含两个空格分隔的整数,n 和 d (1 ≤ n ≤ 105, $$1 \leq d \leq 10^9$$) — 分别是 Kefa 的朋友数量和感觉贫穷的最小金额差异。
接下来n行包含Kefa好友的描述,第(i + 1)行包含第i个类型为mi的好友的描述,si (0 ≤ mi, si ≤ 109) — 分别是金钱数量和友谊系数。
输出
打印可以达到的最大总友谊系数。
示例
输入 #1
4 5 75 5 0 100 150 20 75 1
输出 #1
100
输入 #2
5 100 0 7 11 32 99 10 46 8 87 54
输出 #2
111
注意
在第一个样本测试中,最有利可图的策略是仅由第二个朋友组建公司。在所有其他变体中,友谊的总程度会更差。
在第二个样本测试中我们可以带上所有的朋友。