パイプを有効長が長い方から順に並べます。
同じパイプの本数であれば有効長が長いものから採用するのが最適なので、考えるべきはパイプを有効長が長いものから \(1,2,\dots,N\) 本繋げた場合のみです。

有効長を長い方から並べた列を \(l_1,l_2,\dots,l_N\) としたとき、

• パイプを \(1\) 本繋げた場合の最適解は \(l_1\)
• パイプを \(2\) 本繋げた場合の最適解は \(l_1+l_2-K\)
• パイプを \(3\) 本繋げた場合の最適解は \(l_1+l_2+l_3-2K\)
• \(\dots\)

となります。
これらの最大値は差分が \(l_i-K\) であることを利用すると全体で時間計算量 \(O(N)\) で求められます。

ソートがボトルネックで、全体の時間計算量は \(O(N \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,D,K,C;
  cin >> N >> D >> K >> C;
  vector<ll> l;
  for(ll i=0;i<N;i++){
    ll A,B;
    cin >> A >> B;
    if(B==0){l.push_back(A);}
    else{l.push_back(max(0ll,A-C));}
  }
  sort(l.rbegin(),l.rend());
  ll mxm=0,cur=0;
  for(ll i=0;i<N;i++){
    if(i){cur-=K;}
    cur+=l[i];
    mxm=max(mxm,cur);
  }
  if(mxm>=D){cout << mxm << "\n";}
  else{cout << "-1\n";}
  return 0;
}