Description

Given a set of $n$ stamp denominations and an upper bound $k$ — meaning you may affix at most $k$ stamps to an envelope — find the largest positive integer $m$ such that every value from $1$ to $m$ can be represented using no more than $k$ stamps.

Input Format

The first line contains two integers, the stamp limit $k$ and the number of denominations $n$.

Starting from the second line, except for the last line, each line contains $15$ integers $a_i$. The last line contains at most $15$ integers. In total there are $n$ integers; the $i$-th integer is the value $a_i$ of the $i$-th type of stamp.

Output Format

Output one line with a single integer $m$. If $m$ does not exist, output $0$.

5 2
1 3

13

Hint

Sample Input/Output 1 Explanation

There are denominations $1$ and $3$; you may use at most $5$ stamps. It is easy to form values $1$ through $5$ (just use the $1$-value stamps). The following values are also easy:

• $6 = 3 + 3$.
• $7 = 3 + 3 + 1$.
• $8 = 3 + 3 + 1 + 1$.
• $9 = 3 + 3 + 3$.
• $10 = 3 + 3 + 3 + 1$.
• $11 = 3 + 3 + 3 + 1 + 1$.
• $12 = 3 + 3 + 3 + 3$.
• $13 = 3 + 3 + 3 + 3 + 1$.

However, using $5$ stamps of values $1$ or $3$, it is impossible to form $14$. Therefore, the answer is $13$.

Constraints

• For $100\%$ of the testdata, $1 \leq k \leq 200$, $1 \leq n \leq 50$, $1 \leq a_i \leq 10^4$.

Note

• The statement is translated from NOCOW.

Translated by ChatGPT 5