Key to Success

A television game show prepares a set of prizes for its winner. If the winner's score is $X$, she must choose a subset of the available prizes whose values sum to exactly $X$ dollars.

The organizers already have $n$ spare prizes worth $a_1, a_2, \dots, a_n$ dollars. They do not know the winner's score in advance, so they will buy $m$ more prizes. Their goal is to choose those $m$ prizes so as to maximize the smallest positive integer score that the winner would be unable to collect — that is, the smallest positive integer that cannot be written as the sum of some subset of all prizes (the ones they already have plus the ones they buy).

For example, suppose they already have prizes worth $2$, $3$, and $9$ dollars and may buy $2$ more. If they buy prizes worth $1$ and $7$ dollars, the winner can collect prizes for every score from $1$ to $22$, so the smallest score she could not collect is $23$ — and no other purchase does better. Report that largest achievable smallest-uncollectable score.

The first line contains two integers $n$ and $m$ — the number of prizes the organizers already have and the number they will buy ($0 \le n \le 30$, $1 \le m \le 30$).

The second line contains $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$), the values of the prizes they already have. When $n = 0$, this line is empty.

Print a single integer: over all ways to choose the $m$ prizes to buy, the maximum possible value of the smallest positive integer score that the winner cannot collect prizes for.