양팔 저울

양팔 저울이 하나 있습니다. 저울은 양쪽 접시가 모두 비어 있거나, 왼쪽 접시에 올린 추의 무게 합과 오른쪽 접시에 올린 추의 무게 합이 같을 때에만 수평을 이룹니다.

여러 개의 추가 주어집니다. 이 중 일부를 서로소인 두 그룹으로 나누어 한 그룹은 왼쪽 접시에, 다른 그룹은 오른쪽 접시에 올릴 수 있습니다. 나머지 추는 저울에 올리지 않고 그대로 둡니다. 두 그룹의 무게 합이 같으면 저울은 수평을 이룹니다.

추를 하나 이상 올린 수평 상태만 생각합니다. 그런 상태마다 저울 위에 올라간 추 중 가장 무거운 추가 하나 있습니다. 이 '가장 무거운 추'의 무게를 최대한 크게 만들고 싶습니다. 그 값이 최대 얼마까지 될 수 있는지 구하세요.

첫째 줄에 추의 개수 $n$ ($2 \le n \le 1000$)이 주어집니다. 이어지는 $n$개의 줄에는 각 줄마다 추 하나의 무게가 양의 정수로 주어집니다. 모든 추의 무게 합은 $50000$을 넘지 않습니다.

추를 하나 이상 올리고 수평을 이루는 어떤 배치에 등장할 수 있는 추 가운데 가장 무거운 추의 무게를 정수 하나로 출력합니다. 즉, 수평인 저울 위에 올릴 수 있는 추의 최대 무게를 출력합니다. 그런 배치가 전혀 없으면 $0$을 출력합니다.