Сдачи нет! 1
Ваня опаздывает на автобусы, едущие в ЛКШ. К сожалению, ему недостаточно просто успеть на автобус - по дороге ему ещё нужно купить подарок девушке Кате, у которой скоро день рождения. По дороге ему встретился магазин, где он может купить подарок. Подарок стоит c рублей. У Вани в кошельке есть n купюр, но у продавца нет сдачи, и поэтому Ваня должен набрать нужную сумму без сдачи. Более того, у Вани очень мало времени, деньги нужно достать как можно быстрее, и поэтому Ваня хочет дать продавцу нужную сумму минимальным количеством купюр.
Помогите ему сделать это.
Входные данные
Первая строка содержит три целых неотрицательных числа n, c и k (0 ≤ n ≤ 1000,0 ≤ c ≤ 1000, 1 ≤ k ≤ 10^9
). Далее следуют n чисел a[1]
, a[2]
, ..., a[n]
(1 ≤ a[i]
≤ 1000) - номиналы купюр в том порядке, как они лежат у Вани в кошельке.
Выходные данные
В первую строку выведите одно число m - минимальное количество купюр, которыми Ваня может набрать требуемую сумму. Во вторую строку выведите m чисел - номера купюр, которые должен дать продавцу Ваня. Ване надо будет доставать купюры последовательно из кошелька, поэтому номера должны быть выведены в возрастающем порядке.
Если набрать необходимую сумму без сдачи невозможно, то выведите в выходной файл одно число -1.
Ване безразлично, как набирать требуемую сумму. Поэтому если есть несколько решений, то можете вывести любое. Ваша программа может не обращать внимания на число k.
Примеры
Примечание
В первом примере все возможные варианты решения, отсортированные в лексикографическом порядке следующие:
1 2 (первая и вторая купюры, т.е. купюры номиналом 1 и 4)
2 5 (вторая и пятая купюры, т.е. купюры номиналом 4 и 1)
3 4 (третья и четвёртая купюры, т.е. купюры номиналом 2 и 3)
Вы можете вывести любой из этих вариантов.