/.............................................................................................................................................................................................\
题目解析：hdu的计算机要分成两个学院，现在有n种物品，价值为ai的有bi个，要求把这些东西分成价值总和最为接近的两份，如果不
能平分，大的在前面。
转换为母函数的思路是:把设备排列组合,把所有可能的组合都打出来，然后从总价值的中间开始搜，只要搜到第一个就是了，再用sum-i
就是最靠近的两个价值了。所以输出是sum-i,i。
错误分析: 此题和hdu1085 Holding Bin-Laden Captive!一样，hdu数据只有三个，而此题有多组数据，一开始用结构体写的，因无法
掌握循环，后改用数组输入。
此题和hdu1085比，只要掌握好循环就可以了。
谨记：共提交19次，Wrong Answer了2次（结束时没有return 0），Time Limit Exceeded了8次（数据太大，）， Presentation Error了5次（对输入要求n没掌握好），
Accepted了4次。
\................................................................................................................................................................................................/
#include<stdio.h>
#include <iostream>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<list>
#include<vector>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define MAX 250010
int c1[MAX],c2[MAX];
int A[60];
int B[60];
int main()
{int n,i,j,k;while(scanf("%d", &n) && n>0){memset(A, 0, sizeof(A));memset(B, 0, sizeof(B));int sum = 0;for( i=1; i<=n; i++){scanf("%d %d", &A[i], &B[i]);sum += A[i]*B[i];}for(i=0;i<=sum;i++){c1[i]=0;c2[i]=0;}for(int i=0; i<=A[1]*B[1]; i+=A[1])c1[i] = 1;int l = A[1]*B[1];for(int i=2; i<=n; i++){for( j=0; j<=l; j++)for( k=0; k<=A[i]*B[i]; k+=A[i]){c2[k+j] += c1[j];}l += A[i]*B[i]; //更新范围for( j=0; j<=l; j++) //范围改变了{c1[j] = c2[j];c2[j] = 0;}}for(int i= sum/2; i>=0; i--)if(c1[i] != 0){printf("%d %d\n", sum-i, i);break;}}return 0;
}