Shut the Box

Shut the Box is a one-player game that begins with a set of N pieces labeled from 1 to N. All pieces start out "unmarked". The player is allowed up to T turns, and each turn has an independently chosen value V (typically determined by rolling one or more dice). During a turn, the player must choose a set of currently unmarked pieces whose labels add up to exactly V, and mark them. The game continues until either the player runs out of turns, or a turn is reached at which it is impossible to find a set of unmarked pieces summing to that turn's value V (in which case that turn and all remaining turns are forfeited). The goal is to mark as many pieces as possible; marking every piece is called "shutting the box". Your task is to determine the maximum number of pieces that can be marked for a fixed sequence of turns.

For example, consider a game with 6 pieces and the sequence of turn values 10, 3, 4, 2. The best outcome for that sequence is to mark four pieces in total. One way to achieve this is to use the value 10 to mark pieces 1 + 4 + 5, then use the value 3 to mark piece 3. At that point the game ends, because there is no way to use the turn with value 4 (and the final turn with value 2 is forfeited as well). Another strategy achieving the same total marks pieces 1 + 2 + 3 + 4 with the value 10, and the game then ends on the turn with value 3. No strategy can mark five or more pieces for that sequence.

Hint: avoid enormous arrays or lists if possible.

The input contains several games. Each game begins with a line containing two integers N and T, where $1 \le N \le 22$ is the number of pieces and $1 \le T \le N$ is the maximum number of turns allowed. The next line contains T integers giving the sequence of turn values for the game; each value V satisfies $1 \le V \le 22$. You must read the entire sequence, even though a particular game may end on a failed turn before the end of the sequence. The input ends with a line containing 0 0, which is not part of any game.

For each game, output a single line of the form Game g: k, where g is the game's ordinal (starting from 1, in input order) and k is the maximum number of pieces that can be marked during that game.