Закрой коробку

Игра "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 $\le$ N $\le$ 22) представляет количество фишек, а (1 $\le$ T) — максимальное количество разрешенных ходов. Следующая строка содержит (T) целых чисел, обозначающих последовательность значений ходов для игры; каждое такое значение будет удовлетворять (1 $\le$ V $\le$ 22). Вы должны прочитать всю эту последовательность из входных данных, даже если конкретная игра может закончиться на неудачном ходе до конца последовательности. Набор данных заканчивается строкой, содержащей 0 0.

Выходные данные

Вы должны вывести одну строку для каждой игры, как показано ниже, сообщая порядковый номер игры и максимальное количество фишек, которые могут быть отмечены во время этой игры.

Примеры