#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int INF = 1e9; const ll LINF = 1e18; template ostream& operator << (ostream& out,const pair& o){ out << "(" << o.first << "," << o.second << ")"; return out; } template ostream& operator << (ostream& out,const vector V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; } template ostream& operator << (ostream& out,const vector > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; } template ostream& operator << (ostream& out,const map mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; } /* 問題文============================================================ 今日はハロウィンなので、太郎君は近所の家におかしをもらいに行くことにしました。 近所には、太郎君の家以外に N軒の家があります。 それぞれのi家に行くとおかしをVi個もらえるのですが、 近所のこどもたちに平等におかしを配るため、 すでにおかしをTi個以上持っていると、おかしを一つももらえないことになっています。 太郎君は、最初におかしを一つも持っていないこととし、近所の家を周るのは好きな順番で周ることができるとき、 太郎君がもらえるおかしの最大の個数を求めてください。 同じ家には1回しか回れないとします。 ================================================================= 解説============================================================= ================================================================ */ #define MAX_N 10005 #define MAX_V 20005 bool dp[MAX_N][MAX_V]; ll solve(){ ll res = 0; ll N; cin >> N; vector V(N),T(N); vector VT(N); ll MV = 0; for(auto& in:VT){ cin >> in.first >> in.second; MV = max(MV,in.second);} sort(VT.begin(),VT.end(),[](const pll& p1,const pll& p2){return p1.second < p2.second;}); dp[0][0] = true; for(int i = 0; i < N;i++){ for(int j = 0; j < MV;j++){ if(!dp[i][j]) continue; dp[i+1][j] = true; if(j < VT[i].second) dp[i+1][j+VT[i].first] = true; } } for(int i = MAX_V-1;i>=0;i--){ if(dp[N][i]) res = max(res,(ll)i); } fill(*dp,*dp+MAX_N*MAX_V,false); sort(VT.begin(),VT.end(),[](const pll& p1,const pll& p2){return p1.first < p2.second;}); dp[0][0] = true; for(int i = 0; i < N;i++){ for(int j = 0; j < MV;j++){ if(!dp[i][j]) continue; dp[i+1][j] = true; if(j < VT[i].second) dp[i+1][j+VT[i].first] = true; } } for(int i = MAX_V-1;i>=0;i--){ if(dp[N][i]) res = max(res,(ll)i); } return res; } int main(void) { cin.tie(0); ios_base::sync_with_stdio(false); cout << solve() << endl; return 0; }