#include <stdio.h>
char s[1280][1280];
int largest(int a, int b, int c)
{
    if(a > b && a > c)
        return a;
    else if(b > c)
        return b;
    return c;
}

main()
{
    int n, t[45], total, time; 
    while(true){
        scanf("%d", &n);
        if(n == 0)
            return 0;
        total = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d", &t[i]);
            total += t[i];
        }
        for(int i = 0; i < 1280; i++)
            for(int j = 0; j < 1280; j++)
                s[i][j] = 0;
        s[0][0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = i * 30; j >= 0; j--)
                for(int k = i * 30; k >= 0; k--)
                    if(s[j][k] == 1)
                        s[j + t[i]][k] = s[j][k + t[i]] = 1;
        }
        /*for(int j = 0; j <= 40; j++){
            for(int k = 0; k <= 40; k++)
                printf("%d", s[j][k]);
            printf("\n");
        }*/
        time = 99999;
        for(int j = 0; j <= n * 30; j++)
            for(int k = 0; k <= n * 30; k++)
                if(s[j][k] == 1 && largest(j, k, total - j - k) < time){
                    time = largest(j, k, total - j - k);
                    /*printf("%d %d\n", j, k);*/
                }
        printf("%d\n", time);
    }
}