무게 균형 맞추기

돈을 아끼려고 산타클로스는 순록 외의 다른 동물들도 단기 '긱' 계약으로 썰매를 끌게 하기 시작했다. 그 결과, 특정 여행에서 썰매를 끌기 위해 실제로 나타나는 동물들은 크기가 매우 다양할 수 있다.

지난주에는 버팔로 $2$마리, 들쥐 $37$마리, 슈나우저 1마리가 있었다. 안타깝게도 버팔로 두 마리가 모두 왼쪽에 묶여 있었고, 무게 불균형 때문에 썰매가 비행 중에 뒤집혔다.

앞으로 이런 사고를 막기 위해 산타는 한 여행에 나설 동물들을 두 그룹으로 나누어, 한 그룹에 속한 모든 동물의 무게 합이 다른 그룹에 속한 모든 동물의 무게 합과 같도록 해야 한다. 묶는 작업을 효율적으로 하기 위해 산타는 정수 목표 무게 $t$를 찾고 있으며, $t$보다 가벼운 모든 동물은 한 그룹에, $t$보다 무거운 동물은 다른 그룹에 들어간다. 그러한 $t$가 여러 개라면 가장 작은 것을 원한다. 작은 문제가 하나 있다. 무게가 정확히 $t$인 동물이 있다면 어떻게 해야 할까? 산타는 이렇게 해결한다. 그러한 동물의 수가 짝수라면 두 그룹에 똑같이 나눈다(따라서 무게가 균등하게 분배된다). 하지만 그러한 동물의 수가 홀수라면, 그중 한 마리를 요정들과 함께 장난감을 만드는 일로 보내고(어느 그룹에도 넣지 않는다), 남은(이제 짝수인) 동물들을 두 그룹에 똑같이 나눈다.

입력은 동물들의 무게 목록을 나타낸다. 첫째 줄에는 정수 $m$ ($2 \le m \le 10^5$)이 주어지며, 이는 동물의 수를 나타낸다. 다음 $m$개의 줄에는 각각 양의 정수가 하나씩 주어진다. 이것은 동물들의 무게(온스)이다. $20\,000$온스를 초과하는 동물은 너무 커서 썰매를 끌 수 없으므로, 주어지는 무게는 이 최댓값을 넘지 않는다.

위에서 설명한 가장 작은 정수 목표 무게 $t$를 출력한다. 그러한 정수를 찾는 것이 가능하다는 것이 보장된다.