#include using namespace std; using std::cout; using std::cin; using std::endl; using ll=long long; using ld=long double; ll I=1167167167167167167; ll Q=1e9+7; #define rep(i,a) for (ll i=0;i using _pq = priority_queue, greater>; template ll LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template ll UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;} template bool chmax(T &a,const T &b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end());reverse(v.begin(),v.end());} template void print_tate(vector &v) {rep(i,v.size()) cout<>N; vector> p(N); rep(i,N){ int H,P; cin>>P>>H; p[i]={H,P}; } sort(p.begin(),p.end(),[](auto a,auto b){ return a.first+a.second> dp(N+1,vector(N+2,Q*2)); dp[0][0]=0; rep(i,N) rep(j,i+1){ if(dp[i][j]==Q*2) break; if(dp[i][j]<=p[i].first) chmin(dp[i+1][j+1],dp[i][j]+p[i].second); chmin(dp[i+1][j],dp[i][j]); } rep(i,N+1){ if(dp[N][i+1]==Q*2){ cout<