1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4  5 const int MAX=130000; 6 int c1[MAX],c2[MAX]; 7  8 struct { 9     int val,num;10 }thing[55];11 int n;12 13 int main(){14     while(scanf("%d",&n)!=EOF){15         if(n<0) break;16         int sum=0,tmp;17         for(int i=1;i<=n;i++){18             scanf("%d%d",&thing[i].val,&thing[i].num);19             sum+=(thing[i].val*thing[i].num);20         }21         tmp=sum/2;22         for(int i=0;i<=tmp;i++)23         c1[i]=c2[i]=0;24         for(int i=0,k=0; i<=tmp&&k<=thing[1].num; i+=thing[1].val,k++)25         c1[i]=1;26         for(int i=2;i<=n;i++){27             for(int j=0;j<=tmp; j++){28                 if(c1[j]>=1){29                     for(int k=0,p=0; k+j<=tmp&&p<=thing[i].num; k+=thing[i].val,p++){30                         c2[j+k]+=c1[j];31                     }32                 }33             }34             for(int j=0;j<=tmp;j++){35                 c1[j]=c2[j]; c2[j]=0;36             }37         }38         for(int i=tmp;i>=0;i--){39             if(c1[i]){40                 printf("%d %d\n",sum-i,i);41                 break;42             }43         }44     }45     return 0;46 }