Aizu Online Judge in C++ #Volume25 : 2510 - Twin book report

Aizu Online Judge（AOJ）の過去問から、その提出コードの解答例です。

・問題 "Twin book report"
https://onlinejudge.u-aizu.ac.jp/problems/2510
・双子の読書感想文
僕が作成、提出したコードは、以下のとおりです。

Aizu Online Judge in C++ #Volume25 : 2510 - Twin book report

/*
Aizu Online Judge in C++ #Volume25 : 2510 - Twin book report
https://onlinejudge.u-aizu.ac.jp/problems/2510
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
ll n;P t[1000];
int main(void){
    while(cin>>n,n){
        ll sum=0,sum2=0;
        for(ll i=0;i<n;i++){
            cin>>t[i].first>>t[i].second;
            sum+=t[i].first;
            sum2+=t[i].second;
        }
        sort(t,t+n);
        ll x=sum-t[n-1].first;
        if(t[n-1].first<=x){
            cout<<sum+sum2<<endl;
            continue;
        }
        ll y=t[n-1].first-x,dp[1010]={};
        for(ll i=0;i<n-1;i++){
            ll se=t[i].second;
            for(ll j=y;j>=se;j--){
                dp[j]=max(dp[j],dp[j-se]+se);
            }
        }
        cout<<t[n-1].first*2+sum2-dp[y]<<endl;
    }
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge（AOJ）」です。
http://judge.u-aizu.ac.jp/onlinejudge/