지폐와 룰렛

Kile과 Pogi가 길에서 지폐 $N$장을 주웠다. 주인을 찾을 수 없다는 것을 확인한 두 사람은 지폐를 나눠 갖기로 했다.

두 사람 모두 똑같은 금액을 받고 싶어 하므로, 각자 가져가는 지폐의 금액 합이 서로 같도록 나눈다. 그런 방법 중에서 아무도 가져가지 않고 남는 지폐의 금액 합이 가장 작은 방법을 고른다.

남은 지폐를 길에 그냥 두고 갈 수는 없어서, 두 사람은 근처 카지노로 가서 남은 금액 전부를 빨강에 걸었다. 룰렛은 13에 멈췄고, 이번만큼은 베팅이 적중했다. 카지노는 건 금액의 2배를 지급한다. 지급액은 항상 짝수이므로 두 사람은 이 돈을 정확히 절반씩 나눈다.

두 사람이 각각 집에 가져가는 금액을 구하시오.

첫째 줄에 주운 지폐의 개수 $N$ ($1 \le N \le 500$)이 주어진다.

다음 $N$개의 줄에는 각 줄마다 $i$번째 지폐의 금액 $c_i$가 쿠나(kn) 단위의 양의 정수로 주어진다. 모든 지폐의 금액 합은 $100000$을 넘지 않는다.

두 사람이 각각 집에 가져가는 금액을 정수 하나로 출력한다.

첫 번째 예제에서 Kile은 2 kn, 3 kn, 1 kn짜리 지폐를 가져가고 Pogi는 6 kn짜리 지폐를 가져간다. 남는 지폐가 없어서 카지노에서 받는 돈도 없고, 각자 6 kn을 집에 가져간다.

두 번째 예제에서는 한 사람이 13 kn짜리 지폐를, 다른 한 사람이 2 kn, 3 kn, 8 kn짜리 지폐를 가져가서 둘 다 13 kn씩 갖는다. 5 kn짜리 지폐가 남고 카지노가 10 kn을 지급하므로, 각자 5 kn을 더 받아 18 kn을 집에 가져간다.