题目描述

小镇沿街分布（可以理解为都在数轴上），有n家银行（位置以数轴的坐标表示，金额表示可以被抢走的金额）。

两个绑匪试图分别抢劫一个银行，为了让警方多奔波他们商定选择的两个银行距离不小于d。

请问，符合约定的情况下他们能抢到的总金额最大是多少。

输入格式
输入包含 n+1 行。

第一行包含两个整数 n 和 d，分别表示银行的数量和约定的距离。

接下来 n 行，每行包含两个整数 a 和 b ，分别表示坐标和金额。

输出格式
输出一个数字表示可以获得的最大金额。

数据范围
1≤n≤2∗1051≤n≤2∗105,
1≤d,a,b≤1081≤d,a,b≤108
注意：数据中保证至少存在两个银行之间的距离不小于 dd。！！！！！！！！！！

样例

输入样例1：

6 3
1 1
3 5
4 8
6 4
10 3
11 2

输出样例1：
11

输入样例2：
4 3
1 1
2 100
3 100 
4 1

输出样例2：
2

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N=200010;
typedef pair<int,int> PII;
PII a[N];

int main()
{
    int n,d;
    cin>>n>>d;
    for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;

    sort(a+1,a+1+n);

    int res=0;

    for(int i=1,j=0,maxa=-1e9;i<=n;i++)//maxa+a[].second必须<=0！！！！ 
    {
        while(j+1<i&&a[i].first-a[j+1].first>=d)
        {
            j++;
            maxa=max(maxa,a[j].second);
        }
        res=max(res,a[i].second+maxa);
    }

    cout<<res<<endl;
    return 0;
}