import java.util.*;

public class cakes {
	public static void main(String args[]) {
		Scanner s = new Scanner(System.in);
		while (true) {
			int n = s.nextInt();
			if (n == 0) break;
			HashSet<Integer> poss = new HashSet<Integer>();
			poss.add(0);
			int total = 0;
			for (int i = 0; i < n; i++) {
				HashSet<Integer> temp = new HashSet<Integer>();
				int next = s.nextInt();
				total += next;
				for (int x : poss) {
					temp.add(x + next);
					temp.add(x + (next << 16));
				}
				poss.addAll(temp);
			}
			int bestSoFar = total;
			for (int x : poss) {
				int cur1 = x & ((1 << 16) - 1);
				int cur2 = x >> 16;
				int cur3 = total - (cur1 + cur2);
				int cur = Math.max(cur1, Math.max(cur2, cur3));
				if (bestSoFar > cur) bestSoFar = cur;
			}
			System.out.println(bestSoFar);
		}
	}
}