Shut the Box

Shut the Box는 1부터 N까지 번호가 매겨진 N개의 조각으로 시작하는 1인용 게임입니다. 처음에는 모든 조각이 "표시되지 않은(unmarked)" 상태입니다. 플레이어에게는 최대 T번의 턴이 주어지며, 각 턴에는 독립적으로 정해진 값 V가 있습니다(보통 주사위를 굴려 결정합니다). 한 턴에서 플레이어는 현재 표시되지 않은 조각들 중 번호의 합이 정확히 V가 되는 집합을 골라 표시해야 합니다. 게임은 턴을 모두 사용하거나, 어떤 턴에서 그 턴의 값 V와 합이 정확히 같은 표시되지 않은 조각들의 집합을 찾을 수 없게 될 때까지 계속됩니다(이 경우 해당 턴과 이후의 모든 턴은 버려집니다). 목표는 가능한 한 많은 조각을 표시하는 것이며, 모든 조각을 표시하는 것을 "상자를 닫는다(shutting the box)"라고 합니다. 주어진 고정된 턴 순서에 대해 표시할 수 있는 조각의 최대 개수를 구하세요.

예를 들어 조각이 6개이고 턴 값의 순서가 10, 3, 4, 2인 게임을 생각해 봅시다. 이 순서에서 얻을 수 있는 최선의 결과는 조각 4개를 표시하는 것입니다. 한 가지 방법은 값 10으로 조각 1 + 4 + 5를 표시하고, 값 3으로 조각 3을 표시하는 것입니다. 이 시점에서 값 4인 턴을 사용할 방법이 없어 게임이 끝납니다(마지막 값 2인 턴도 함께 버려집니다). 같은 개수를 얻는 다른 전략으로는 값 10으로 조각 1 + 2 + 3 + 4를 표시하고 값 3인 턴에서 게임이 끝나는 방법이 있습니다. 하지만 이 순서로는 어떤 방법으로도 조각 5개 이상을 표시할 수 없습니다.

힌트: 가능하면 지나치게 큰 배열이나 리스트는 사용하지 마세요.

입력은 여러 개의 게임으로 이루어집니다. 각 게임은 두 정수 N과 T가 담긴 줄로 시작하며, $1 \le N \le 22$은 조각의 개수, $1 \le T \le N$은 허용되는 최대 턴 수입니다. 다음 줄에는 그 게임의 턴 값 순서를 나타내는 T개의 정수가 주어지며, 각 값 V는 $1 \le V \le 22$를 만족합니다. 특정 게임이 순서의 끝에 도달하기 전에 실패한 턴에서 끝나더라도, 순서 전체를 반드시 입력에서 읽어야 합니다. 입력은 0 0이 담긴 줄로 끝나며, 이 줄은 어떤 게임에도 포함되지 않습니다.

각 게임마다 Game g: k 형식의 한 줄을 출력합니다. 여기서 g는 게임의 순번(입력 순서대로 1부터 시작)이고, k는 그 게임에서 표시할 수 있는 조각의 최대 개수입니다.