← 返回题目列表

Codeforces · 279/D

D. 变量的最小数量

中文机器翻译题面 查看原题

你有一个正整数序列 a1, a2, ..., an。序列中的所有数字都是不同的。让我们修复变量集 b1, b2, ..., bm。最初,每个变量 bi (1 ≤ i ≤ m) 包含零值。考虑以下由 n 个操作组成的序列。

第一个操作是将 a1 的值分配给某个变量 bx (1 ≤ x ≤ m)。以下 n - 1 个操作中的每一个都将值分配给某个变量,该值等于存储在变量 bi 和 bj 中的值之和 (1 ≤ i, j, y ≤ m)。此时,在第 t 次操作中分配的值必须等于 at。对于每个操作,重新选择数字 y、i、j。

你的任务是找到变量 m 的最小数量,以便这些变量可以帮助你执行所描述的操作序列。

输入

第一行包含整数 n (1 ≤ n ≤ 23)。第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ak ≤ 109)。

保证序列中的所有数字都是不同的。

输出

在一行中打印一个数字 - 变量 m 的最小数量,这样这些变量可以帮助您执行所描述的操作序列。

如果在任何 m 处都无法执行操作序列,则打印 -1。

示例

输入 #1

5
1 2 3 6 8

输出 #1

2

输入 #2

3
3 6 5

输出 #2

-1

输入 #3

6
2 4 8 6 10 18

输出 #3

3

注意

在第一个示例中,您可以使用两个变量 b1 和 b2 来执行以下操作序列。

1. b1 := 1;
2. b2 := b1 + b1;
3. b1 := b1 + b2;
4. b1 := b1 + b1;
5. b1 := b1 + b2。