Альфред хочет купить игрушечного лося, который стоит c долларов. В магазине совсем нет сдачи, поэтому ему необходимо набрать ровно c долларов, ни больше и ни меньше. У него есть n монет. Чтобы набрать c долларов он использует следующий алгоритм: обозначим через S множество используемых сейчас монет. Изначально множество S пусто. Альфред последовательно добавляет в множество S новые монеты, каждый раз выбирая такую, что после её добавления суммарная стоимость монет не превышает c. Среди всех таких монет он выбирает наиболее дорогую. Если таких монет не существует, а суммарная стоимость множества S всё ещё меньше c, то Альфред сдаётся и уходит. Обратите внимание, что Альфред только добавляет монеты в множество S и никогда их оттуда не убирает.

Как программист, вы, скорее всего, знаете, что алгоритм Альфреда может не набрать множество монет с нужной суммой c, даже если оно существует. Например, пусть у Альфреда есть одна монета достоинством $3, одна монета достоинством $4 и две монеты достоинством $5 долларов, а игрушечный лось стоит $12. Следуя своему алгоритму, Альфред возьмёт обе монеты достоинством $5 и на этом остановится, так и не набрав нужную сумму. С другой стороны, набрать $12 долларов можно было, взяв по одной монете достоинством $3, $4 и $5.

Боб попытался убедить Альфреда в недостатках его алгоритма, но тот отказывается в это верить. Боб решил дать Альфреду ещё монет (в дополнение к тем, что уже есть у Альфреда), чтобы его алгоритм перестал работать. Боб может дать Альфреду любое количество монет любой стоимости (единственное условие, что каждая монета должна стоить целое положительное число долларов). Разрешается дать несколько монет одинаковой стоимости. Боб просит вас найти подходящее множество монет минимальной суммарной стоимости. Если решения не существует, выведите «Greed is good». Можете считать, что если ответ существует, то он положительный, то есть без дополнительных монет алгоритм Альфреда работает на данном множестве монет и для данной стоимости лося.