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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 15;

1 ≤ k ≤ 10⁸;

1 ≤ h_i ≤ k;

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

4 10
4 6 4 6

4 4 6 6