#include <stdio.h>
#define N 64
int len,num,sum,n;
int da[N];
char use[N];
void sort()//选择排序,用快排反而TLE
{
int i,j,t,max;
for (i=0;i<n;i++)
{
t=da[i];
max=i;
for (j=i+1;j<n;j++)
{
if (t<da[j])
{
t=da[j];
max=j;
}
}
if (max-i)
{
da[max]=da[i];
da[i]=t;
}
}
}
int dfs(int pre,int leave,int tatol)
{
int i;
if (leave==0)
{
if (tatol==num-2)
{
return 1;
}
i=0;
while (use[i])
{
i++;
}
use[i]=1;
if (dfs(i+1,len-da[i],tatol+1))
{
return 1;
}
use[i]=0;
return 0;
}
else
{
if (pre==n-1)//这种情况说明:搜索到结尾,而且未组成要搜索的目标挷长,所以结束本长度的搜索
{
return 0;
}
for (i=pre;i<n;i++)//未组成目标长度,但是还有未搜索到得小棒,继续搜;
{
if (use[i])
{
continue;
}
if ((da[i]==da[i-1])&&!use[i-1])
{
continue;
}
if (da[i]>leave)
{
continue;
}
use[i]=1;
if (dfs(i,leave-da[i],tatol))
{
return 1;
}
use[i]=0;
}
return 0;
}
}
void main()
{
int i,flag;
while (scanf("%d",&n)&&n)
{
memset(use,0,sizeof(use));
sum=0;
for (i=0;i<n;i++)
{
scanf("%d",&da[i]);
sum=sum+da[i];
}
sort();//从大到小排序
flag=0;
for (len=da[0];len<=sum/2;len++)//原棒长度不可能小于最长的小棒的长度,所以从最长短棒开始搜素
{ //但是搜索sum/2~~sum之间的也无意义
if (sum%len==0)
{
num=sum/len;
use[0]=1;
if (dfs(0,len-da[0],0))
{
printf("%d\n",len);
flag=1;
break;
}
use[0]=0;
}
}
if (!flag)
{
printf("%d\n",sum);
}
}
}