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} у вхідному файлі не накладається. \textbf{Примітка} У першому прикладі усі можливі варіанти розв'язку, відсортовані у лексикографічному порядку наступні: \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