まず、中継局を \(3\) つ以上設置する意味はありません。そのうち座標が最も小さい \(1\) つを排除することで合計のコストを下げることができます。

以降、座標の差が \(D\) 以内の中継局を \(2\) つ採用し、コストの合計を最小化するという問題を解きます。

尺取り法 によってデータ構造を操作する方針が最も楽でしょう。

• 多重集合 \(ms\) を用意する。
• まず、中継局の候補を座標の昇順にソートする。
• \(l=1,2,\dots,N\) について、以下を繰り返す。
  • 左から \(l\) 番目にある中継局の候補の座標を \(x\) としたとき、座標 \(x+D\) 以下の中継局の候補をすべて \(ms\) に追加する。
  • \(ms\) のうち小さい方から \(2\) つの和が、解の候補となる。
  • 左から \(l\) 番目の中継局を排除する。

中継局の候補を適切に \(ms\) に追加することで、追加と削除を全ての中継局についてそれぞれ \(1\) 回に抑えることができます。

「任意の要素を \(1\) つ追加する」「任意の要素を \(1\) つ削除する」「小さい方から \(2\) つの和を求める」が簡単に実行できるデータ構造はいくつかありますが、 C++ では multiset を使うと実装が楽になります。詳細は実装例を参考にしてください。

本解法の時間計算量は \(O(N \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pl=pair<ll,ll>;

int main(){
  ll N,D;
  cin >> N >> D;
  vector<pl> vp(N);
  for(auto &nx : vp){
    cin >> nx.first >> nx.second;
  }
  sort(vp.begin(),vp.end());
  ll res=8e18,r=0;
  multiset<ll> ms;
  for(ll l=0;l<N;l++){
    while(r<N && vp[r].first-vp[l].first<=D){
      ms.insert(vp[r].second);
      r++;
    }
    if(ms.size()>=2){
      auto it=ms.begin();
      ll v=(*it);
      it++;
      res=min(res,v+(*it));
    }
    ms.erase(ms.find(vp[l].second));
  }
  if(res>4e18){res=-1;}
  cout << res << "\n";
  return 0;
}