Задача . E. Жадный выбор

Вася занимается исследованием применения жадных алгоритмов в различных областях. Сейчас он пытается изучить применимость жадного алгоритма для задачи о сдаче. Имеется набор из n различных номиналов монет, причем монет каждого номинала имеется неограниченное количество. Задача состоит в том, чтобы набрать сумму x наименьшим числом монет. Жадный алгоритм на каждом шаге берет монету наибольшего номинала, не превосходящего x. Очевидно, что если в наборе номиналов присутствует 1, то любую сумму x можно набрать жадным алгоритмом. Однако жадный алгоритм не всегда даст оптимальное представление данной суммы, т.е. представление, содержащее наименьшее количество монет. К примеру, если имеются номиналы {1, 3, 4} и требуется набрать сумму 6, то жадный алгоритм построит представление 4 + 1 + 1, в то время как оптимальным является представление 3 + 3, содержащее на монету меньше. По заданному набору номиналов определите, существует ли такая сумма x, которую жадный алгоритм наберет неоптимальным способом. Если такая сумма существует, то найдите наименьшую из таких сумм.