Задача E. Доклад с картинками

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

Текстовый процессор, который использует Вася, работает следующим образом. Каждая страница имеет высоту k сантиметров. Картинки располагаются одна за другой, начиная с первой страницы. Если очередная картинка не входит на текущую страницу целиком, то текстовый процессор переходит на следующую страницу.

Зная высоту каждой картинки в сантиметрах hi, определите порядок следования картинок, при котором полученный документ будет иметь наибольшее количество страниц.

В тестовом примере имеется 4 картинки с высотами 6 см, 4 см, 6 см и 4 см. Высота страницы составляет 10 см. Одно из оптимальных решений — расположить картинки в следующем порядке: 4, 4, 6, 6. Тогда первые две картинки окажутся на первой странице, а оставшиеся две картинки займут по одной странице каждая. Таким образом, весь доклад займёт 3 страницы.

Формат входного файла

Входной файл содержит два целых числа — n k, за которыми следуют n целых чисел — h1… hn.

Формат выходного файла

Выходной файл должен содержать n целых чисел — высоты картинок в оптимальном порядке. Если имеется несколько оптимальных ответов, выведите любой из них.

Ограничения

1 ≤ n ≤ 15;

1 ≤ k ≤ 108;

1 ≤ hi ≤ k;

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 10
4 6 4 6

4 4 6 6

0.036s 0.007s 15