e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin kəməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Məsələlər

Сдачи нет! 2

Сдачи нет! 2

Ваня опаздывает на автобусы, едущие в ЛКШ. К сожалению, ему недостаточно просто успеть на автобус - по дороге ему ещё нужно купить подарок девушке Кате, у которой скоро день рождения. По дороге ему встретился магазин, где он может купить подарок. Подарок стоит c рублей. У Вани в кошельке есть n купюр, но у продавца нет сдачи, и поэтому Ваня должен набрать нужную сумму без сдачи. Более того, у Вани очень мало времени, деньги нужно достать как можно быстрее, и поэтому Ваня хочет дать продавцу нужную сумму минимальным количеством купюр.

Помогите ему сделать это.

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

Первая строка входного файла содержит три целых неотрицательных числа: n, c и k (0n1000,0c1000, 1k1000000000). Далее следуют n чисел a1, a2, ..., an (1ai1000) - номиналы купюр в том порядке, как они лежат у Вани в кошельке.

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

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

Если набрать необходимую сумму без сдачи невозможно, то выведите в выходной файл одно число -1.

Теперь Ване не безразлично, как набирать требуемую сумму. У Вани есть любимое число k, и поэтому, если решение существует, вы должны вывести k-ое в лексикографическом порядке. Лексикографический порядок в этой задаче мы будем понимать как обычно для последовательностей из m чисел, а именно: все различные решения сортируем по номеру первой входящей в решение купюры, при равных номерах первой купюры - по второй и т.д. Гарантируется, что если решение существует, то k не превосходит общего количества решений. Решения нумеруются начиная с 1; решения, отличающиеся порядком купюр, считаем за одно решение (в выходной файл вы должны в любом случае выводить номера купюр в возрастающем порядке). Обращаем внимание, что, если решения не существует, то никаких дополнительных ограничений на значение k во входном файле не налагается.

Примечание

В первом примере все возможные варианты решения, отсортированные в лексикографическом порядке следующие:

  • 1 2 (первая и вторая купюры, т.е. купюры номиналом 1 и 4)
  • 2 5 (вторая и пятая купюры, т.е. купюры номиналом 4 и 1)
  • 3 4 (третья и четвёртая купюры, т.е. купюры номиналом 2 и 3)

Нам по условию подходит второй вариант.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
5 5 2
1 4 2 3 1
Çıxış verilənləri #1
2
2 5