贪心x

dp√

code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <map>
#include <cstring>
#include <cmath>
#include <unordered_set>
#include <set>
#include <utility>
#include <climits>

#define int long long
#define PII pair<int , int>
#define inf 0x3f3f3f
using namespace std;

typedef struct
{
    int w , s;
}node;

bool cmp(node a , node b)
{
    return a.s + a.w < b.w + b.s;
}

int n;

void solve() 
{
    cin >> n;
    vector<node> a(n + 1);
    for (int i = 1 ; i <= n ; i ++ ) cin >> a[i].w >> a[i].s;

    sort(a.begin() + 1 , a.end() , cmp);

    int ans = 0;
    int nowTopWeight = 0;

    for (int i = 1 ; i <= n ; i ++ ) 
    {
        int temp = nowTopWeight - a[i].s;
        ans = max(ans , temp);
        nowTopWeight += a[i].w;
    }

    cout << ans << endl;
}

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    solve();
    return 0;
}