시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 14 3 3 50.000%

문제

대한 레슬링 협회는 다가오는 올림픽 선발전을 대비하기 위해 소속 선수들을 두 팀으로 나누려고 한다.

모든 선수는 두 팀 중 하나에 소속되어야 한다. 또, 두 팀에 소속된 선수의 차이는 1을 넘어갈 수 없다. 마지막으로, 각 팀의 몸무게의 합의 차이는 최소가 되어야 한다.

모든 선수들의 몸무게가 주어졌을 때, 위의 조건을 지키면서 팀을 나눈 다음, 각 팀의 몸무게의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 선수의 수 n이 주어진다. 다음 n개 줄에는 각 선수의 몸무게가 주어진다. 모뭄게는 1보다 크거나 같고, 450보다 작거나 같은 정수이다. 협회에 소속된 선수의 수는 100명을 넘지 않는다.

출력

각 팀의 몸무게의 합을 공백으로 구분해 출력한다. 합이 작은 것을 먼저 출력한다. 

예제 입력

3
100
90
200

예제 출력

190 200

힌트