/*hdu1455dfs

*/

#include<bits/stdc++.h>

using namespace std;

typedef unsigned int ui;

typedef long long ll;

typedef unsigned long long ull;

#define pf printf

#define prime1 1e9+7

#define prime2 1e9+9

#define scand(x) scanf("%llf",&x)

#define f(i,a,b) for(int i=a;i<=b;i++)

#define scan(a) scanf("%d",&a)

#define dbg(args) cout<<#args<<":"<<args<<endl;

#define pb(i) push_back(i)

#define ppb(x) pop_back(x)

#define maxn 100

int a[maxn],used[maxn],n;

int tot,ans,target;

int flag;

void dfs(int now,int finish,int pos)

{

    if(flag)return;

    if(finish==tot/target)

    {

        flag=;

        return;

    }

//    if(num+a[n]>target)return;//最短的一根木棍和当前木棍无法拼成，则搜索失败

    f(i,pos,n)

    {

        if(used[i])continue;

        if(a[i]+now>target)continue;

        used[i]=true;

        if(now+a[i]==target)

        {

            dfs(,finish+,);

        }

        else

        {

            dfs(now+a[i],finish,i+);

        }

        if(flag)return;

        used[i]=false;

        if(!now)return;//数根已经可以拼成target长度，但是剩余木棍中较长的一根作为首选无法达成要求，说明第一根会被废弃

        while(a[i]==a[i+]&&i+<=n)i++;//前面用相同长度的木棍，无法拼成，则后面用同样长度的也不能拼成

    }

}

int main()

{

    std::ios::sync_with_stdio(false);

    while(scan(n)==&&n)

    {

        flag=;

        tot=;

        ans=;

        f(i,,n)

        {

            scan(a[i]);

            tot+=a[i];

        }

        sort(a+,a+n+,greater<int>());//降序 ，总是现用最长的木棍最为第一根检查是否可以拼接

        f(i,a[],tot) //实际上最长不可能超过tot/2,

        {

            if(tot%i==)

            {

                memset(used,,sizeof(used));

                target=i;

                dfs(,,);

                if(flag)

                {

                    ans=target;

                    break;

                }

            }

        }

        if(!flag)pf("%d\n",tot);

        else pf("%d\n",ans);

    }

 }