学步园

//就是把一组整数序列分成2份，要使和的差值最小
//就是以整个序列和的一半为容量进行背包
//DP[i]以i为容量的背包最多选择的整数序列的和
//DP[i] = max{DP[i],DP[i - V[i]] + V[i]}
//这题没过啊，不知道为什么超时
#include <iostream>
#include <cstring>
using namespace std;

int N;
int V[5000];
int DP[250000];

int value,num;
int main()
{
	while(cin>>N)
	{
		if(N == -1)
			break;
		int count = 1;
		for(int i = 1; i <= N; i++)
		{
			cin>>value>>num;
			while(num--)
			{
				V[count++] = value;
			}
		}
		count --;
		int sum = 0;
		for(int i = 1; i <= count; i++)
		{
			sum += V[i];
		}
		sum /= 2;

		memset(DP,0,sizeof(DP));
		for(int i = 1; i <= sum; i++ )
		{
			for(int j = sum; j >= V[i]; j--)
			{
				DP[j] = max(DP[j],DP[j - V[i]] + V[i]);
			}
		}

		int A,B;
		B = DP[sum];
		A = sum*2 - B;
		cout<<A<<" "<<B<<endl;
	}
	return 0;
}