팀 디저트

다이어트는 외롭고 지루할 수 있습니다. 그래서 Olympic Slimmers Inc.(OSI)라는 회사는 다이어트를 팀 스포츠로 만들었습니다. 이 회사의 첫 번째 게임이 바로 팀 디저트(Team Dessert) 챌린지입니다.

긴 탁자 위에 디저트 접시들이 한 줄로 놓여 있고, 각 접시에는 무게가 적혀 있습니다. 참가자들은 두 팀으로 나뉘며, 두 팀이 번갈아 가며 디저트를 하나씩 가져갑니다. 예를 들어 Red 팀과 Blue 팀이 있고 Blue 팀이 먼저 시작한다면, 가져가는 순서는 Blue, Red, Blue, Red, ... 가 됩니다.

디저트를 고르는 데에는 한 가지 규칙이 있습니다. 자신의 차례에는 줄의 양쪽 끝 중 하나에 있는 디저트만 가져갈 수 있습니다. 따라서 매 선택은 두 접시 중 하나를 고르는 것입니다(마지막 차례에는 접시가 하나만 남아 선택의 여지가 없습니다).

• 두 팀의 인원수는 최대한 같게 맞춥니다. 인원수를 똑같이 나눌 수 없으면 인원이 더 많은 팀이 먼저 시작합니다.
• 모든 참가자는 정확히 하나의 디저트를 가져갑니다.
• 디저트의 개수는 참가자 수와 같습니다.

디저트 무게의 합이 더 작은 팀이 승리합니다.

디저트가 놓인 순서대로 무게가 주어질 때, 먼저 시작하는 팀의 최선의 전략을 구하세요. 상대 팀도 최선으로 플레이한다고 가정할 때, 먼저 시작하는 팀이 확실하게 보장할 수 있는 최소 무게 합을 계산하면 됩니다. (이 값을 보장한다고 해서 반드시 승리하는 것은 아닙니다.)

입력은 여러 개의 테스트 케이스로 이루어져 있습니다.

각 테스트 케이스의 첫 줄에는 참가자 수를 나타내는 정수 $N$이 주어집니다($1 \le N \le 1000$). $N = 0$이면 입력의 끝을 의미하며, 이는 테스트 케이스가 아닙니다.

그 다음 줄들에는 디저트가 탁자에 놓인 순서대로 $N$개의 무게가 주어집니다. 각 무게 $W$는 $1 \le W \le 100$을 만족합니다. 한 줄에는 무게가 적어도 하나 이상 있으며, 어떤 줄도 80자를 넘지 않습니다. 무게들은 하나 이상의 공백으로 구분되고, 줄의 앞뒤에 공백이 있을 수 있습니다.

각 테스트 케이스마다, 먼저 시작하는 팀이 (상대 팀이 최선으로 플레이한다고 가정할 때) 확실하게 보장할 수 있는 최소 디저트 무게 합을 한 줄에 하나의 정수로 출력하세요.