← 返回题目列表

Codeforces · 580/B

B. 科发公司

中文机器翻译题面 查看原题

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

注意

在第一个样本测试中,最有利可图的策略是仅由第二个朋友组建公司。在所有其他变体中,友谊的总程度会更差。

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