Brian Fulk is struggling with a really poor computer for a couple of days. Now he is trying to write a very simple program which receives a positive integer *x* and returns some of its multiples, say, *a*_{1}*x*,...,*a*_{N}*x*. However, even such a simple task is not easy on this computer since it has only three arithmetic operations: addition, subtraction and left shift.

Let us describe the situation in more details. Initially the computer stores only a given positive integer *x*. The program Brian is writing will produce *a*_{1}*x*,..., *a*_{N}*x*, where *a*_{1},...,*a*_{N} are given multipliers, using only the following operations:

- addition of two values,
- subtraction of two values, and
- bitwise left shift (left shift by n bits is equivalent to multiplication by 2
^{n}).

The program should not generate any value greater than 42*x*; under this constraint he can assume that no overflow occurs. Also, since this computer cannot represent negative values, there should not be subtraction of a greater value from a smaller value.

Some of you may wonder where the number 42 comes from. There is a deep reason related to the answer to life, the universe and everything, but we don't have enough space and time to describe it.

Your task is to write a program that finds the shortest sequence of operations to produce the multiples *a*_{1}*x*,...,*a*_{N}*x* and reports the length of the sequence. These numbers may be produced in any order.

Here we give an example sequence for the first sample input, in a C++/Java-like language:

a = x << 1; // 2x b = x + a; // 3x c = a + b; // 5x d = c << 2; // 20x e = d - b; // 18x

The first line specifies *N*, the number of multipliers. The second line contains *N* integers *a*_{1},..., *a*_{N}, each of which represents a multiplier of *x*.

You can assume that *N* ≤ 41 and 2 ≤ *a _{i}* ≤ 42 (1 ≤

Output in a line the minimum number of operations you need to produce the values *a*_{1}*x*,...,*a*_{N}*x*.

3 3 5 18

5

1 29

4

4 12 19 41 42

8

Source: ACM-ICPC Japan Alumni Group Winter Camp
, Day 3, Tokyo, Japan, 2009-02-23

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/