D. The Minimum Number of Variablestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou've got a positive integer sequence a1, a2, ..., an. All numbers in the sequence are distinct. Let's fix the set of variables b1, b2, ..., bm. Initially each variable bi (1 ≤ i ≤ m) contains the value of zero. Consider the following sequence, consisting of n operations.The first operation is assigning the value of a1 to some variable bx (1 ≤ x ≤ m). Each of the following n - 1 operations is assigning to some variable by the value that is equal to the sum of values that are stored in the variables bi and bj (1 ≤ i, j, y ≤ m). At that, the value that is assigned on the t-th operation, must equal at. For each operation numbers y, i, j are chosen anew.Your task is to find the minimum number of variables m, such that those variables can help you perform the described sequence of operations.InputThe first line contains integer n (1 ≤ n ≤ 23). The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ak ≤ 109).It is guaranteed that all numbers in the sequence are distinct.OutputIn a single line print a single number — the minimum number of variables m, such that those variables can help you perform the described sequence of operations.If you cannot perform the sequence of operations at any m, print -1.ExamplesInput51 2 3 6 8Output2Input33 6 5Output-1Input62 4 8 6 10 18Output3NoteIn the first sample, you can use two variables b1 and b2 to perform the following sequence of operations.  b1 := 1;  b2 := b1 + b1;  b1 := b1 + b2;  b1 := b1 + b1;  b1 := b1 + b2. 
Input51 2 3 6 8
Output2
['bitmasks', 'dp', '*2200']