/*

     题意：若干小木棍，是由多条相同长度的长木棍分割而成，问最小的原来长木棍的长度；

     DFS剪枝：剪枝搜索的好题！TLE好几次，终于剪枝完全！

         剪枝主要在4和5：4 相同长度的木棍不再搜索；5 若新的搜索连第一条都没组合出来，直接break；

     详细解释：http://blog.csdn.net/lyy289065406/article/details/6647960

                 http://www.cnblogs.com/devil-91/archive/2012/08/03/2621787.html

     这题虐我千百遍，我待她如。。        656K    0MS

     博客随笔第100篇，纪念一下:)

 */

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <map>

 #include <set>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 const int MAXN = ;

 const int INF = 0x3f3f3f3f;

 int a[MAXN];

 bool vis[MAXN];

 int sum;

 int n, cnt;

 bool cmp(int x, int y)

 {

     return x > y;

 }

 bool DFS(int len, int ans, int num, int s)

 {

     if (num == cnt)    return true;

     int pre = -;

     for (int i=s; i<=n; ++i)

     {

         if (vis[i] || a[i] == pre)    continue;        //Cut 4

         vis[i] = true;

         if (ans + a[i] < len)

         {

             if (DFS (len, ans + a[i], num, i) == true)  return true;

             else    pre = a[i];

         }

         else if (ans + a[i] == len)

         {

             if (DFS (len,  , num+, ) == true)  return true;

             else    pre = a[i];

         }

         vis[i] = false;

         if (ans == )    break;        //Cut 5

     }

     return false;

 }

 int main(void)        //POJ 1011 Sticks

 {

     //freopen ("POJ_1011.in", "r", stdin);

     while (scanf ("%d", &n) ==  && n)

     {

         sum = ;    memset (vis, , sizeof (vis));

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

         {

             scanf ("%d", &a[i]);    sum += a[i];

         }

         sort (a+, a++n, cmp);                //Cut 1

         bool flag = false;

         for (int i=a[]; i<=sum-i; ++i)        //Cut 2

         {

             if (sum % i == )                //Cut 3

             {

                 cnt = sum / i;

                 if (DFS (i, , , ) == true)

                 {

                     flag = true;

                     printf ("%d\n", i);    break;

                 }

             }

         }

         if (!flag)    printf ("%d\n", sum);

     }

     return ;

 }

 /*

 6

 5

 */