I智乃挖坑（二分答案+二重差分）

显然，对于这个问题，越挖到最后越可能挖出边界。答案具有单调性。

对挖出边界需要的挖坑次数二分，对二分到的mid进行check

二重差分： 在区间[l, r]上，加首项为a，公差为d的等差数列，等效于在一重差分和二重差分上做如下操作。

差分还原为原数组：“二重差分的前缀和是一重差分，一重差分的前缀和是原数组”

check中的diff数组维护二重差分，故对check中的diff数组求两次前缀和，即得到原数组。然后对每个位置判断是否超出边界即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
using pii = pair<ll, ll>;

bool check(int goal, vector<pii>& arr, ll h, ll n, vector<ll>& diff) {
    for (int i=1; i<=goal; i++) {
        auto[idx, val] = arr[i];
        int l, r; ll a, d;
        if (idx > 1) {
            if (idx-val+1 >= 1) {
                l = idx-val+1;
                a = -1;
            }
            else {
                l = 1;
                a = -val + idx-1;
            }
            r = idx-1;
            d = -1;
            ll cnt = (r-l);
            diff[l] += a;
            diff[l+1] += d-a;
            diff[r+1] -= (d + (a+cnt*d));
            diff[r+2] += a+cnt*d;
        }
        {
            l = idx; r = min(n, idx+val-1);
            a = -val; d = 1;
            ll cnt = (r-l);
            diff[l] += a;
            diff[l+1] += d-a;
            diff[r+1] -= (d + (a+cnt*d));
            diff[r+2] += a+cnt*d;
        }
    }
    for (int i=1; i<=n; i++) diff[i] += diff[i-1];
    for (int i=1; i<=n; i++) diff[i] += diff[i-1];
    for (int i=1; i<=n; i++) {
        if (diff[i]+h < 0) return true;
    }
    return false;
}

void solve() {
    int n, m; ll h; cin>>n>>m>>h;
    vector<pii> arr(m+1);
    for (int i=1; i<=m; i++) cin>>arr[i].first>>arr[i].second;
    int l=1, r=m, mid, ans = -1;

    vector<ll> diff(n+5, 0);
    while (l <= r) {
        mid = l + (r-l) / 2;
        fill(diff.begin(), diff.end(), 0);
        if (check(mid, arr, h, n, diff)) {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    if (ans == -1) cout<<"No"<<'\n';
    else {
        cout<<"Yes"<<'\n';
        cout<<ans<<'\n';
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();

    return 0;
}