Bit Days

Problem Description

There are $n$ machines in a workshop. Machine $i$ must be repaired exactly $a_i$ times.

The workshop works in days numbered $1, 2, 3, \ldots$.

On each day, at most one repair can be done. However, not every machine is available on every day.

For a positive integer $d$, write $d$ in binary. Machine $i$ is available on day $d$ if the $(i-1)$-th bit of $d$ is equal to $1$.

Here bits are numbered from $0$ starting from the least significant bit.

For example:

• on day $1$, binary representation is $1$, so only machine $1$ is available;
• on day $2$, binary representation is $10$, so only machine $2$ is available;
• on day $3$, binary representation is $11$, so machines and are available;

Your task is to find the minimum number of days after which it is possible to complete all repairs.

In other words, find the smallest integer $D$ such that the repairs can be scheduled during days $1, 2, \ldots, D$, with at most one repair per day, and every machine $i$ repaired exactly $a_i$ times.

Input Format

The first line contains one integer $n$ ($1 \le n \le 20$) --- the number of machines.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($$) --- the required number of repairs for each machine.

Output Format

Output one integer --- the minimum possible value of $D$.

Scoring

2
1 1

2