#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cstdlib>
#include <ctime>

using namespace std;

int n,tot,best,v[41];
char a[41][1201][1201];

char dp(int k,int v1,int v2)
{
  char &ret=a[k][v1][v2];
  if (ret) return ret;
  ret=1;
  if (k==n){
    int v3=tot-v1-v2;
    int i=max(v1,max(v2,v3));
    if (i<best) best=i;
  }else{
    dp(k+1,v1+v[k],v2);
    dp(k+1,v1,v2+v[k]);
    dp(k+1,v1,v2);
  }
}

int main()
{
  int i;
  while(1){
    scanf("%d",&n);
    if (!n) break;
    tot=0;
    for(i=0;i<n;i++){
      scanf("%d",&v[i]);
      tot+=v[i];
    }
    memset(a,0,sizeof(a));
    best=10000000;
    dp(0,0,0);
    printf("%d\n",best);
  }
  return  0;
}