eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сдачи нет! 2

Сдачи нет! 2

Ваня опаздывает на автобусы, едущие в ЛКШ. К сожалению, ему недостаточно просто успеть на автобус - по дороге ему ещё нужно купить подарок девушке Кате, у которой скоро день рождения. По дороге ему встретился магазин, где он может купить подарок. Подарок стоит \textbf{c} рублей. У Вани в кошельке есть \textbf{n} купюр, но у продавца нет сдачи, и поэтому Ваня должен набрать нужную сумму без сдачи. Более того, у Вани очень мало времени, деньги нужно достать как можно быстрее, и поэтому Ваня хочет дать продавцу нужную сумму минимальным количеством купюр. Помогите ему сделать это. \InputFile Первая строка входного файла содержит три целых неотрицательных числа: \textbf{n}, \textbf{c} и \textbf{k} (\textbf{0} ≤ \textbf{n} ≤ \textbf{1000},\textbf{0} ≤ \textbf{c} ≤ \textbf{1000}, \textbf{1} ≤ \textbf{k} ≤ \textbf{1000000000}). Далее следуют \textbf{n} чисел \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n} (\textbf{1} ≤ \textbf{a_i} ≤ \textbf{1000}) - номиналы купюр в том порядке, как они лежат у Вани в кошельке. \OutputFile В первую строку выходного файла выведите одно число \textbf{m} - минимальное количество купюр, которыми Ваня может набрать требуемую сумму. Во вторую строку выведите \textbf{m} чисел - номера купюр, которые должен дать продавцу Ваня. Ване надо будет доставать купюры последовательно из кошелька, поэтому номера должны быть выведены в возрастающем порядке. Если набрать необходимую сумму без сдачи невозможно, то выведите в выходной файл одно число \textbf{-1}. Теперь Ване не безразлично, как набирать требуемую сумму. У Вани есть любимое число \textbf{k}, и поэтому, если решение существует, вы должны вывести \textbf{k}-ое в лексикографическом порядке. Лексикографический порядок в этой задаче мы будем понимать как обычно для последовательностей из \textbf{m} чисел, а именно: все различные решения сортируем по номеру первой входящей в решение купюры, при равных номерах первой купюры - по второй и т.д. Гарантируется, что если решение существует, то \textbf{k} не превосходит общего количества решений. Решения нумеруются начиная с \textbf{1}; решения, отличающиеся порядком купюр, считаем за одно решение (в выходной файл вы должны в любом случае выводить номера купюр в возрастающем порядке). Обращаем внимание, что, если решения не существует, то никаких дополнительных ограничений на значение \textbf{k} во входном файле не налагается. \Note В первом примере все возможные варианты решения, отсортированные в лексикографическом порядке следующие: \begin{itemize} \item \textbf{1 2} (первая и вторая купюры, т.е. купюры номиналом \textbf{1} и \textbf{4}) \item \textbf{2 5} (вторая и пятая купюры, т.е. купюры номиналом \textbf{4} и \textbf{1}) \item \textbf{3 4} (третья и четвёртая купюры, т.е. купюры номиналом \textbf{2} и \textbf{3}) \end{itemize} Нам по условию подходит второй вариант.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
5 5 2
1 4 2 3 1
Выходные данные #1
2
2 5