1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 55; 7 const int INF = 1000000000; 8  9 int n, sum;10 int vo[maxn * maxn * 100];11 int dp[maxn * maxn];12 int solve() {13     memset(dp, 0, sizeof(dp));14     for(int i = 1; i < n; i++) {15         for(int j = sum; j >= vo[i]; j--) {16             dp[j] = max(dp[j], dp[j - vo[i]] + vo[i]);17         }18     }19     int mid = (sum + 1) >> 1;20     int i;21     for(i = mid; i <= sum; i++) {22         if(dp[i] == i) break;23     }24     return i;25 }26 27 int main() {28     int m;29     int a, b;30     while(scanf("%d",&m) ) {31         if(m < 0) break;32         n = 1;33         sum = 0;34         for(int i = 1; i <= m; i++) {35             scanf("%d %d",&a, &b);36             sum += a * b;37             for(int k = 1; k <= b; k *= 2) {38                 vo[n++] = k * a;39                 b -= k;40             }41             if(b) vo[n++] = b * a;42         }43         int ans = solve();44         printf("%d %d\n",ans, sum - ans);45     }46     return 0;47 }