Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 4 Contest LoginRegister Exam
Problem 1074. -- Tug of War

Tug of War

Time Limit: 3 Sec  Memory Limit: 64 MB
Submit: 13  Solved: 3


Tug of war is a contest of brute strength, where two teams of people pull in opposite directions on a rope. The team that succeeds in pulling the rope in their direction is declared the winner. A tug of war is being arranged for the office picnic. The picnickers must be fairly divided into two teams. Every person must be on one team or the other, the number of people on the two teams must not differ by more than one, and the total weight of the people on each team should be as nearly equal as possible.


The first line of each case contains n, the number of people at the picnic. Each of the next n lines gives the weight of a person at the picnic, where each weight is an integer between 1 and 450. There are at most 100 people at the picnic.


For each test case, your output will consist of a single line containing two numbers: the total weight of the people on one team, and the total weight of the people on the other team. If these numbers differ, give the smaller number first.

Sample Input


Sample Output

190 200



Waterloo local 2000.09.30



한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin