原题链接：https://www.luogu.com.cn/problem/P8806

01背包问题

//Prim算法
#include <bits/stdc++.h>

#define ll long long
//5484660609
const ll N = 1e6;
ll le[N];
bool ok[N];//判断这个点是否删除掉了
ll dp[N];

struct ii{
    ll w;
    ll v;
    friend bool operator<(ii &w1,ii &w2){
        return w1.w + w1.v <= w2.w + w2.v;
    }
}pp[N];

int main(){
    ll n;
    ll res = -1;
    std::cin >> n;
    for(ll i = 1; i <= n; i ++) std::cin >> pp[i].w >> pp[i].v;
    std::sort(pp + 1,pp + 1 + n);
    for(ll i = 1; i <= n; i ++){
        for(ll j = pp[i].w + pp[i].v; j >= pp[i].w;j --){
            dp[j] = std::max(dp[j],dp[j - pp[i].w] + pp[i].v);
            res = std::max(res,dp[j]);
        }
    }
    std::cout << res << "\n";
    return 0;
}