#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

int Solve(const VI &time) {

  int sum = 0;
  for (size_t i = 0; i < time.size(); i++)
    sum += time[i];

  VVI used(sum+1, VI(sum+1));
  used[0][0] = 1;

  for (size_t i = 0; i < time.size(); i++) {
    for (int j = sum; j >= 0; j--) {
      for (int k = sum; k >= 0; k--) {
	if (used[j][k]) {
	  used[j + time[i]][k] = 1;
	  used[j][k + time[i]] = 1;
	}
      }
    }
  }

  int best = sum;
  for (int j = 0; j <= sum; j++) {
    for (int k = 0; k <= sum; k++) {
      if (used[j][k]) {
	int total_time = max(sum - j - k, max(j, k));
	if (total_time < best) best = total_time;
      }
    }
  }

  return best;
}

int main() {
  while (1) {
    int n;
    cin >> n;
    if (n == 0) break;

    VI time(n);
    for (int i = 0; i < n; i++) cin >> time[i];
    cout << Solve(time) << endl;
  }
}