//好像我也没怎么剪枝，只是判断如果相同的两根只取一根……
可能是测试数据过于简单了吧，再bt一些就AC不了了~

5742954 gamy 1011 Accepted 240K 16MS C++ 1172B 2009-08-24 15:35:00 

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

int LEN,NUM;
int sticks[70];
int cp[70];
bool used[70];
int n;

bool dfs(int s,int f)
{
	

	while((sticks[s]==n)||(!used[s]))
	{
		s++;
		f=s+1;
	}
	if(s>=NUM)
		return true;
	int i;
	int pre=-1;
	for(i=f;i<=NUM;i++)
	{
		if(used[i]&&(sticks[s]+sticks[i]<=n)&&(sticks[i]!=pre))
		{
			pre=sticks[i];
			sticks[s]+=sticks[i];
			used[i]=false;
			if(dfs(s,i))
				return true;
			sticks[s]-=sticks[i];
			used[i]=true;
		}
	}
	return false; 
}

void intcpy()
{
	int i;
	for(i=1;i<=NUM;i++)
		sticks[i]=cp[NUM-i+1];
}

int main()
{
	cin>>NUM;
	while(NUM!=0){
	LEN=0;
	int i;
	for(i=1;i<=NUM;i++)
	{
		cin>>cp[i];
		LEN+=cp[i];
	}
	sort(cp+1,cp+NUM+1);
	n=0;
	for(i=1;i<=NUM;i++)
		if(n<cp[i])
			n=cp[i];
    int len=LEN;
	bool flag=false;
	for(;n<=len;n++)
	{         
		if(len%n==0)
		{
			memset(used,true,sizeof(used));
			LEN=len;
			intcpy();
			sticks;
			if(dfs(1,2))
			{
				cout<<n<<endl;
				flag=true;			
			}
			if(flag)
				break;
		}
		if(flag)
			break;
	}
	cin>>NUM;
	}
	return 0;
}