P2725 [USACO3.1] Stamps

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.

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 one line with a single integer $m$. If $m$ does not exist, output $0$.

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