Закрий коробку
"Shut the Box" — це гра для одного гравця, яка починається з набору фішок, пронумерованих від 1 до N. Усі фішки спочатку "непозначені" (на зображенні праворуч, непозначені фішки знаходяться у верхньому положенні). У версії, яку ми розглядаємо, гравцеві дозволено до T ходів, причому кожен хід визначається незалежно обраним значенням V (зазвичай визначається кидком одного або кількох кубиків). Під час ходу гравець повинен позначити набір фішок, які наразі непозначені, і чиї числові мітки в сумі дають точно V, і позначити їх. Гра продовжується або до тих пір, поки у гравця не закінчаться ходи, або до того моменту, коли під час одного ходу стане неможливо знайти набір непозначених фішок, які в сумі дають задане значення V (у цьому випадку цей хід і всі наступні ходи втрачаються). Мета полягає в тому, щоб позначити якомога більше фішок; позначення всіх фішок відоме як "закриття коробки". Ваша мета — визначити максимальну кількість фішок, які можна позначити за фіксовану послідовність ходів.
Як приклад, розглянемо гру з 6 фішками і наступною послідовністю ходів: 10, 3, 4, 2. Найкращий результат для цієї послідовності — позначити загалом чотири фішки. Це можна досягти, використовуючи значення 10 для позначення фішок 1+4+5, а потім використовуючи значення 3 для позначення фішки 3. На цьому етапі гра закінчиться, оскільки немає способу точно використати хід зі значенням 4 (останній хід зі значенням 2 також буде втрачено). Альтернативна стратегія для досягнення тієї ж кількості позначених фішок — використати значення 10 для позначення чотирьох фішок 1+2+3+4, з грою, що закінчується на ході зі значенням 3. Але не існує жодного способу позначити п'ять або більше фішок з цією послідовністю.
Підказка: уникайте величезних масивів або списків, якщо це можливо.
Вхідні дані
Кожна гра починається з рядка, що містить два цілі числа, N і T, де 1 ≤ N ≤ 22 представляє кількість фішок, а 1 ≤ T ≤ N представляє максимальну кількість ходів, які будуть дозволені. Наступний рядок містить T цілих чисел, що позначають послідовність значень ходів для гри; кожне таке значення задовольняє 1 ≤ V ≤ 22. Ви повинні прочитати всю цю послідовність з вхідних даних, навіть якщо конкретна гра може закінчитися на невдалому ході до кінця послідовності. Набір даних закінчується рядком, що містить 0 0.
Вихідні дані
Ви повинні вивести один рядок для кожної гри, як показано нижче, вказуючи порядковий номер гри та максимальну кількість фішок, які можуть бути позначені під час цієї гри.