Здачі немає! 2#4072

Здачі немає! 2

1 секунда

64 мегабайти

Складна

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

Допоможіть йому це зробити.

Вхідні дані

Перший рядок вхідного файлу містить три цілих невід'ємних числа: $n$ , $c$ та $k$ ( $0 \leq n \leq 1000$ 0 \leq n \leq 1000, $0 \leq c \leq 1000$ 0 \leq c \leq 1000, $1 \leq k \leq 1000000000$ 1 \leq k \leq 1000000000). Далі йде $n$ чисел $a_{1}$ a_1, $a_{2}$ a_2, ... , $a_{n}$ a_n ( $1 \leq a_{i} \leq 1000$ 1 \leq a_i \leq 1000) — номінали купюр у тому порядку, як вони лежать у Вані у гаманці.

Вихідні дані

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

Якщо набрати необхідну суму без здачі неможливо, то виведіть у вихідний файл одне число $- 1$ .

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

Приклади

Приклад 1

Примітка

У першому прикладі усі можливі варіанти розв'язку, відсортовані у лексикографічному порядку наступні:

$12$ (перша та друга купюри, тобто купюри номіналом $1$ та $4$ )
$25$ (друга та п'ята купюри, тобто купюри номіналом $4$ та $1$ )
$34$ (третя та четверта купюри, тобто купюри номіналом $2$ та $3$ )

Нам за умовою підходить другий варіант.