[http://online-judge.uva.es/p/v100/10032.html 원문보기]
----
인기도:B(A,B,C), 성공률:낮음(낮음,보통,높음), 레벨:2(1~4)

=== About TugOfWar ===
사무실 야유회에서 줄다리기를 하기로 했다. 야유회에 참가한 사람들을 두 편으로 공평하게 나눈다. 모든 사람들이 둘 중 한 편에 참여해야 하며, 두 편의 사람 수는 한 명이 넘게 차이가 나면 안 된다. 그리고 양 편에 속한 사람들 체중의 총합 차를 최소한으로 줄여야 한다.

=== Input ===
첫번째 줄에는 테스트 케이스의 수가 입력되고, 그 다음 줄은 빈 줄이다.

각 케이스의 첫번째 줄에는 야유회에 참가한 사람의 수인 n이 입력된다. 그리고 그 밑으로 n줄에 걸쳐서 야유회에 참가한 사람의 체중이 입력된다. 이 값은 1 이상 450 이하의 정수이다. 야유회에 참가하는 사람의 수는 최대 100명이다.

서로 다른 테스트 케이스 사이에는 빈 줄이 하나씩 입력된다.

=== output ===
각 테스트 케이스마다 한 줄씩의 결과를 출력하며, 각 줄마다 두 개씩의 정수가 출력된다. 첫번째 수는 한편에 속한 사람들의 체중의 총합, 다른 수는 다른 편에 속한 사람들의 체중의 총합이다. 이 두 값이 서로 다르면 작은 값을 먼저 출력한다.

두 개의 서로 다른 케이스에 대한 결과는 빈 줄로 구분한다.

=== Sample Input ===
{{{
5

3
100
90
200

6
45
55
70
60
50
75

4
92
56
47
82

5
2
3
4
7
8

4
50
50
100
200
}}}

worst case(입력자료 크기로만) 입력은 TugOfWarInput 참조
=== Sample Output ===
{{{
190 200
175 180
138 139
12 12
150 250
}}}

=== 풀이 ===
|| 작성자 || 사용언어 || 개발시간 || 코드 ||
|| [상협] || Python || 3시간 || [TugOfWar/남상협] ||
|| 신재동 || Python || 14분 || [TugOfWar/신재동] ||
|| [강희경] || Python || 2일 || [TugOfWar/강희경] ||
|| [김회영] || C || 4시간 || [TugOfWar/김회영] ||
|| JuNe || Python || 1시간 || Seminar:TugOfWar/JuNe ||
|| [이승한] || C || 오래. || [TugOfWar/이승한] ||
|| [문보창] || C++ || . || [TugOfWar/문보창] ||
=== 쓰레드 ===
원문에는 테스트가 너무 적은 것 같아 2개 더 추가합니다. --재동

번역 실수~ 140을 450으로 수정했음 -- 재선

테스트케이스를 하나 더 추가하였습니다. --[강희경]
 테스트의 출력이 틀렸다. {{{~cpp 12 12}}}가 아니라 {{{~cpp 11 13}}}이다. --재동 
  제가 짠 프로그램에도 그렇게 나오는데, 손으로 풀면 4+8, 2+3+7이렇게 되네요 --[강희경]
  {{{~cpp 12 12}}} 아닌가요? 총합차이가 최소인데요 -- 재선
   {{{~cpp 12 12}}}가 맞는 것 같군. 그럼 문제가 생각보다 어려워지는데... --재동
이런식의 문제 대략 어려운데;; - [이승한]
 사람수를 고려안하고 했음. 낭패. ㅠ.ㅠㅋ - [이승한]
----
[문제분류]