Vasya 计划在家里举办一场果汁品鉴派对。这里有 $n$ 种来自 Vasya 最喜爱的世界各地的不同果汁，例如法国的卢瓦尔河谷（Loire Valley）、加利福尼亚的纳帕谷（Napa Valley）和智利的中央山谷（Valle Central）。他购买了 $c_i$ 升第 $i$ 种果汁。
为了在派对开始前储存这些果汁，Vasya 需要购买一些特制的桶。每个桶都足够大，可以装下任意数量的果汁。然后，他按照以下特殊规则将不同种类的果汁分配到这些桶中：
- 所有种类的所有果汁都必须分配到桶中。
- 每个桶中最多只能包含两种不同种类的果汁。
- 任意两个桶中的果汁总量必须相同。
请注意，桶中的果汁量可以是非整数。允许某些桶只包含一种果汁。每种果汁可以分配到任意数量的桶中。两种不同种类的果汁可以按任意比例在桶中混合。
由于桶的价格昂贵，Vasya 希望购买最少数量的桶，以便能够按照上述规则储存所有果汁。请帮助他找到这个最小值。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 20$) —— Vasya 喜欢的不同果汁种类数。
第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$)，其中第 $i$ 个整数表示 Vasya 拥有的第 $i$ 种果汁的升数。
输出格式
输出一个整数：Vasya 为了能够按照上述规则储存所有果汁而必须购买的最少桶数。
样例
输入格式 1
3 1 1 1
输出格式 1
2
输入格式 2
5 1 2 1 1 1
输出格式 2
3
输入格式 3
1 100
输出格式 3
1
说明
在第一个样例中，Vasya 有 3 种果汁，每种 1 升。他可以将第一种果汁全部放入第一个桶中，将第二种果汁全部放入第二个桶中，并在每个桶中各加入 0.5 升第三种果汁。