Migrated from Lutece 215 吴队长征婚

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

吴队长征婚这件事因为请客而没有传出去(虽然他忘了请一个队吃饭)，于是吴队长高兴地玩起了木棒。吴队长拿了一些长度相同的木(guang)棒(gun)，随机的把它们截成了$N$段，每一段最长50。现在他想把这些木棒还原成原来的状态，但是他忘记了原来的木棒有多少根，也忘记了每一根有多长。请帮助他设计一个程序，帮他计算之前木棒可能的最小长度。输入数据保证每一段木棒长度都大于0。

Input

输入有多组数据，每组数据分为两行。
第一行一个整数$N$，表示截断之后木棒的个数。$1 \le N \le 64$
第二行$N$个整数，表示截断之后的每一段小木棒的长度。
当N=0时，表示输入结束。

Output

每组数据输出一个整数占一行，表示原木棒可能的最小长度。

Samples

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

6
5

Resources

2015 UESTC Training for Search Algorithm and String