Sum It Up

You are given a target total $t$ and a list of $n$ positive integers. Find every distinct way to pick numbers from the list whose values add up to exactly $t$. Each number may be used in a single sum only as many times as it appears in the list, and a single number by itself counts as a sum. For example, with $t = 4$ and the list $[4, 3, 2, 2, 1, 1]$, there are four distinct sums equal to $4$: $4$, $3+1$, $2+2$, and $2+1+1$.

The input contains one or more test cases, one per line. Each line gives the total $t$, then the count $n$, then the $n$ list values $x_1, x_2, \ldots, x_n$, all separated by single spaces. A line whose $n$ is $0$ marks the end of the input and is not processed. For every real test case, $1 \le t < 1000$, $1 \le n \le 12$, and each $1 \le x_i < 100$. The list values are given in nonincreasing order and may contain repeats.

For each test case, print a line Sums of <t>: (the words Sums of, a space, the total, and a colon). Then print each qualifying sum on its own line, joining the terms with +; if there are none, print a single line NONE. Inside a sum the numbers appear in nonincreasing order, and a value may repeat only as often as it occurs in the list. Order the sums in decreasing lexicographic order of their terms: compare by the first term, break ties by the second term, then the third, and so on. Within a test case all sums must be distinct.