Description

Given an envelope on which at most $N$ stamps may be affixed, determine, for given $K$ types of stamps (with $N+K \le 15$ and assuming an unlimited supply of each type), how to design the stamp denominations to obtain the largest value $\mathsf{MAX}$ such that every postage value from $1$ to $\mathsf{MAX}$ can be formed.

For example, when $N=3$, $K=2$: if the denominations are $1$ fen and $4$ fen, then every postage value between $1\sim 6$ can be formed (and, of course, also $8$, $9$, and $12$); if the denominations are $1$ fen and $3$ fen, then every postage value between $1\sim 7$ can be formed. One can verify that when $N=3$ and $K=2$, $7$ is the largest consecutive postage value that can be obtained, so $\mathsf{MAX}=7$, with denominations $1$ fen and $3$ fen.

Input Format

Two integers, representing $N$ and $K$.

Output Format

Output a total of $2$ lines.

On the first line, output the chosen denominations in ascending order.

On the second line, output MAX=S, where $S$ denotes the maximum consecutive postage value.

3 2

1 3
MAX=7

Hint

Translated by ChatGPT 5