题目描述

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 $50$ 个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过 $64$ 的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

样例

输入样例：

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

输出样例：

6
5

样例解释

第一组数据：有 9 节木棍，长度分别为 5, 2, 1, 5, 2, 1, 5, 2, 1。
可以拼成 3 根长度为 6 的木棒：每根由 5+1, 2+2+2, 5+1 等组合方式得到，但实际只需保证每根长度 6 且所有木棍用完。
最小可能原始长度是 6。

第二组数据：有 4 节木棍，长度分别为 1, 2, 3, 4。
可以拼成 1 根长度为 10 的木棒，但也可以拼成多根。
最小可能原始长度是 5（拼成两根：1+4 和 2+3）。

数据范围

• 每组木棍数不超过 64
• 每节木棍长度不超过 50
• 多组数据，以 0 结束

时空限制

• 时间限制：1 秒
• 空间限制：64 MB