1 #include <cstring> 2 #include <iostream> 3 #include <algorithm> 4 5 using namespace std; 6 7 long long dp[250010]; 8 int v[5500][2]; 9 10 int main() 11 { 12 int n; 13 while(cin>>n&&n>0) 14 { 15 long long int sum=0; 16 long long int req; 17 memset(v,0,sizeof(v)); 18 for(int i=0;i<n;i++) 19 { 20 cin>>v[i][0]>>v[i][1]; 21 sum+=v[i][0]*v[i][1]; 22 } 23 req=sum/2; 24 memset(dp,0,sizeof(dp)); 25 for(int i=0;i<n;i++) 26 { 27 for(int t=0;t<v[i][1];t++) 28 for(int vv=req;vv>=v[i][0];vv--) 29 { 30 dp[vv]=max(dp[vv-v[i][0]]+v[i][0],dp[vv]); 31 } 32 } 33 cout<<sum-dp[req]<<" "<<dp[req]<<endl; 34 } 35 return 0; 36 }