#include<iostream>
using namespace std;
#define N 300
int used[N],a[65],b[65],dflag[65];
int answer, num;
int judge(int i,int j,int w)
 
{
int flag=0;int k=i+1;//for(int r=0;r<64;r++)cout<<a[r]<<" ";cout<<'\n'<<endl<<"another";for( r=0;r<200;r++)cout<<used[r]<<" ";cout<<'\n'<<endl<<"next";
int all=0;
for(int s=0;s<num;s++)//递归的跳出条件；
{if(a[s]==0)flag++;}//因为a[k]都已经置0当所有的数字都搜索完

if((flag==num)&&(used[j-1]==answer))//（1）        //且used[]最后一位(因为最后有个used[j]==answer的判断
    return 1;                              // 该过程中j++了一次 故此处判断used[j-1]

else  //（1）
{

  if(used[j]==answer)//（2）
	 { 	 
       for(int n=0;n<=w;n++)a[dflag[n]]=0;//一次搜索完成后将该组中最小的数置0；
         for( n=0;n<num;n++)dflag[n]=0;
	    i++;j++;k=i+1;w=0;
     	while(!a[i])i++;dflag[0]=i;
	    used[j]=a[i];//a[i]=0;//将一组中的开始数据，放入used[]中并将在a[]中的该位置0；
		if(!judge(i,j,w))return 0;
		else return 1;
	 }

 else if(used[j]<answer)//（2）
   {
	 int check;
	   check=answer-used[j];
	   for(k=dflag[w]+1;k<num;k++)//从标志位后的第一位开始搜索，选择合适的加入used[]中；
		{if((a[k]<=check)&&(a[k]!=0))break;}
	                                              
     if(k<num)//（3）

{   dflag[++w]=k;used[j+1]=used[j]+a[k];
	j++;
         if(!judge(i,j,w))return 0;
        else return 1;
}
    else //（3）
  {  
         if(j>0)//（4）
	 
 {    
	if(dflag[w]>=(num-1))//（5）
	{
		if(w==1)return 0;//（6）
		else//（6）
		{ 
			if(a[dflag[w]]!=a[dflag[w-1]])//（7）
		{
	        w--;int r=dflag[w];dflag[w]++; 
	 while(((!a[dflag[w]])||(a[dflag[w]]==a[dflag[w]-1])) &&(dflag[w]<num))dflag[w]++;
	 //此处将dflag[w]后推,后面与其相等则跳过
		 used[j+1]=used[j]-a[dflag[w+1]]-a[r]+a[dflag[w]];j++;     
         if(!judge(i,j,w))return 0;
          else return 1;
		}
		if(a[dflag[w]]==a[dflag[w-1]])//（7）
		{
          w=w-2;int r=dflag[w];dflag[w]++;
			 
	     while(((!a[dflag[w]])||(a[dflag[w]]==a[dflag[w]-1])) &&(dflag[w]<num))dflag[w]++;
		 used[j+1]=used[j]-a[dflag[w+1]]-a[dflag[w+2]]-a[r]+a[dflag[w]];j++;     
         if(!judge(i,j,w))return 0;
          else return 1;

		}
		}
	}
	if(dflag[w]<(num-1))//（5）
	{	
		int t=dflag[w];dflag[w]++;//用t将dflag[w]（当前位）的值存放起来
	while(((!a[dflag[w]])||(a[dflag[w]]==a[dflag[w]-1]))&&dflag[w]<num)dflag[w]++;
	//此处跳出是可能是正常跳出，也可能是dflag[w]==num，但都进行下面的操作，再次递归时再判断

	{
		used[j+1]=used[j]-a[t]+a[dflag[w]];j++;
	    if(!judge(i,j,w))return 0;
          else return 1;
		  }
	}
	
}

else if(j==0)return 0;//（4）  //used[]中装入的第一个数就无法满足条件
  }
}
}

}

int main()
{for(int s=0;s<100;s++)
	
{
	int i,j,temp;
	
	int maxlen,alllen;
	
	   maxlen=0;alllen=0;
		cout<<"input the number of sticks"<<endl;
	cin>>num;if(num==0)return 0;

{   for(i=0;i<65;i++)
	{a[i]=0;b[i]=0;dflag[i]=0;}
   cout<<"input the value of sticks"<<endl;
	for(i=0;i<num;i++)
	{cin>>b[i];if(b[i]==0)return 0;}
	
	    for(i=0;i<num;i++)
		for(j=0;j<num;j++)
			if(b[j]<b[j+1]){temp=b[j];b[j]=b[j+1];b[j+1]=temp;}
		
	for(i=0;i<num;i++)
	{alllen+=b[i];}
	for(int answer_wait=b[0];answer_wait<=alllen;answer_wait++)

	{  if(alllen%answer_wait==0)
	   {
		answer=answer_wait;//cout<<answer<<"is answer"<<endl;
		for(i=0;i<num;i++){a[i]=b[i];}//cout<<"b[0] is"<<b[0]<<endl;cout<<"a[0] is"<<a[0]<<endl;
		for(i=0;i<N;i++){used[i]=0;}used[0]=a[0]; 
		 for(i=0;i<num;i++)dflag[i]=0;                           
		if(judge(0,0,0)){cout<<answer<<endl;break;}
	    
	}
	}
	
		
	}
	}
return 0;
}	
//本人就只用了一个递归的函数，所有的操作（包括判断和长度相加）都在这个递归函数中进行
//读起来有些烦琐，这个程序一直没有过，但是所有BT的数据包括自己搭配的数据也都过了
//算法想了好多遍也没有什么问题，A不掉也无所谓了，反正得到了应该得到的
//附上几组数据大家试试
//12
//40 40 40 40 39 38 37 36 8 7 6 5
//答案84

//16
//40 40 40 39 38 37 36 20 20 7 6 6 4 1 1 1
//答案84

//64
//40 40 30 35 35 26 15 40 40 40 40 40 40 40 40 40 40 40 40 40 40 

//40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40 

//40 25 39 46 40 10 4 40 40 37 18 17 16 15 40 40 40 40 40 40 40 

//40

//答案454