The output should contains the smallest possible length of original sticks, one per line.
Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output

6
5

      （1）编程思路。

      定义数组int* stick=new int[n];来保存所输入的n根木棒的长度，数组bool* visit=new bool[n]; 来记录对应的n根木棒是否被用过，初始时值全为false。

      由于木棒越长，拼接灵活度越低，因此搜索前先对所有的棒子按降序排序，即将stick数组的元素按从大到小排序。

      编写一个递归的搜索函数bool dfs(int* stick,bool* visit,int len,int InitLen,int s,int num)，其中参数 len表示当前正在组合的棒长、InitLen表示所求的目标棒长、s（stick[s]）表示搜索的起点、num代表已用的棒子数量。如果按InitLen长度拼接，可以将n根木棒全用掉，则函数返回true，搜索成功；否则函数返回false，表示InitLen不可能是所求的最短原始棒长。

      令InitLen为所求的最短原始棒长，maxlen为给定的棒子堆中最长的棒子（maxlen=stick[0]）;，sumlen为这堆棒子的长度之和，那么所要搜索的原始棒长InitLen必定在范围[maxlen，sumlen]中。

      实际上，如果能在[maxlen，sumlen-InitLen]范围内找到最短的InitLen，该InitLen必也是[maxlen，sumlen]范围内的最短；若不能在[maxlen，sumlen-InitLen]范围内找到最短的InitLen，则必有InitLen=sumlen。因此，可以只在[maxlen，sumlen-InitLen]范围内搜索原始棒长。即搜索的循环为：for(int InitLen=maxlen;InitLen<=sumlen-InitLen;InitLen++)

      在搜索时，为提高效率，还可以进行剪枝。具体是：

      1）由于所有原始棒子等长，那么必有sumlen%Initlen==0，因此，若sumlen%Initlen!=0，则无需对Initlen值进行搜索判断。

      2）由于所有棒子已降序排列，在DFS搜索时，若某根棒子不合适，则跳过其后面所有与它等长的棒子。

      3）对于某个目标InitLen，在每次构建新的长度为InitLen的原始棒时，检查新棒的第一根棒子stick[i]，若在搜索完所有stick[]后都无法组合，则说明stick[i]无法在当前组合方式下组合，不用往下搜索（往下搜索只会令stick[i]被舍弃），直接返回上一层。

      （2）源程序

#include<iostream>

#include<algorithm>  

using namespace std; 

int n;  // 木棒数量 

int cmp(const void* a,const void* b) 

{ 

      return *(int*)b-*(int*)a; 

} 

bool dfs(int* stick,bool* visit,int len,int InitLen,int s,int num);

int main() 

{ 

    while(cin>>n && n) 

    { 

       int* stick=new int[n]; 

       bool* visit=new bool[n]; 

       int sumlen=0,i;

          bool flag;

       for(i=0;i<n;i++) 

       { 

           cin>>stick[i]; 

           sumlen+=stick[i]; 

           visit[i]=false; 

       } 

       qsort(stick,n,sizeof(stick),cmp); 

       int maxlen=stick[0];  

       flag=false; 

       for(int InitLen=maxlen;InitLen<=sumlen-InitLen;InitLen++)

       {    

            if(!(sumlen%InitLen) )              // 剪枝（1）