各 \(l\) について \(\displaystyle \sum_{i=l}^{r}C_i \leq M\) を満たすような最大の \(r\) を求めて \(l\) を動かしたときの \(X_r-X_l\) の最大値を求めたいです。

\(C\) は正なので、 \(l\) を昇順に動かして尺取り法により \(r\) を求められます。

\(C\) の累積和を求めておくことで判定が容易になり、全体で時間計算量は \(\mathrm{O}(N)\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    long long m;
    cin >> n >> m;
    vector<int> x(n);
    vector<long long> c(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> c[i];
    vector<long long> sum(n + 1);
    for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + c[i];
    int r = 0;
    int ans = 0;
    for (int l = 0; l < n; ++l) {
        while (r < n && sum[r + 1] - sum[l] <= m) r++;
        ans = max(x[r - 1] - x[l], ans);
    }
    cout << ans << endl;
}