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

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

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

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

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

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

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

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시간	TugOfWar/JuNe
이승한	C	오래.	TugOfWar/이승한
문보창	C++	.	TugOfWar/문보창

원문에는 테스트가 너무 적은 것 같아 2개 더 추가합니다. --재동

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

테스트케이스를 하나 더 추가하였습니다. --강희경
이런식의 문제 대략 어려운데;; - 이승한

문제분류