#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
 + ;
bool vis[maxn];
int sticks[maxn];
int CurLen;
int n;
int Remain;///每一次都去重置为
bool DFS(int id, int Lack)///传入的参数为上次选择了哪个木棍、当前还缺多少才能组成一个新的目标木棍
{
    ){///已经组成一个新的木棍了，

        Remain -= CurLen;
        ) return true;///如果当前总长为0，说明此方案可行！

        int which;
        ; vis[which]==true; which++);///由于是排好序，我们取第一个没有使用过的木棍开始下一次的搜索

        vis[which] = true;///标记

        if( DFS(which, CurLen-sticks[which]) ) return true;///开始新一轮搜索

        vis[which] = false;///记得标记回来

        Remain += CurLen;///赋值回来！搜索题代码应当注意的地方！

    }else{
        for(int i=id; i<n; i++){
             && (sticks[i]==sticks[i-] && !vis[i-])) continue;///剪枝:排序后，如果有数字不能返回true，说明在此刻选
                                                                      ///择同样的数字也是一样的结果，所以跳过

            if(vis[i] || Lack < sticks[i]) continue;

            Lack -= sticks[i];
            vis[i] = true;

            if( DFS(i, Lack) ) return true;

            Lack += sticks[i];
            vis[i] = false;

            if(sticks[i] == Lack) break;///剪枝:如果当前if成立，说明刚刚的DFS肯定是
                                        ///到达过Lack==0的，既然不返回true，那么说明
                                        ///此方案不行，不必继续往下面搜下去了！
        }
    }
    return false;
}

bool cmp(int fir, int sec){ return fir > sec; }

int main(void)
{
    while(~scanf("%d", &n) && n){
        ;

        ; i<n; i++){
            scanf("%d", &sticks[i]);
            tot += sticks[i];///累计总和
            vis[i] = false;
        }

        sort(sticks, sticks+n, cmp);///排序方便剪枝

        bool ok = false;
        ]; Len<=tot/; Len++){
            ){
                Remain = tot;///将Remain重置，代表当前搜索状态下总长度还剩多少，如果为0说明成功
                CurLen = Len;///全局变量记录当前枚举的是哪个因数，方便深搜操作
                , Len)){
                    printf("%d\n", Len);
                    ok = true;
                    break;
                }
            }
        }

        if(!ok) printf("%d\n", tot);
    }
    ;
}