공평하게 팀 나누기

면접 대비

시간 제한1초메모리 제한128 MB

요약

N명을 인원 차이가 1 이하인 두 팀으로 나누어 두 팀의 총 무게 차이가 최소가 되게 하고, 두 총합을 오름차순으로 출력한다.

문제

학생회장은 학교 축제에서 학우들의 친목을 다지기 위해 줄다리기 경기를 열려고 한다.

경기의 형평성을 위해 두 팀의 인원 수 차이는 1명 이하가 되어야 하며, 이 조건 아래에서 두 팀의 몸무게 합의 차이가 최소가 되도록 팀을 나누려고 한다.

이렇게 나눈 두 팀의 몸무게 합을 각각 구하시오.

첫째 줄에 줄다리기에 참여하는 사람의 수 $N$ ( $1 \le N \le 100$ )이 주어진다.

이어지는 $N$ 개의 줄에는 각 사람의 몸무게 $K$ ( $1 \le K \le 450$ )가 한 줄에 하나씩 주어진다.

두 팀의 몸무게 합을 작은 값부터 순서대로 공백으로 구분하여 출력한다.