Уже много лет космические корабли взлетают не с поверхности Земли,
а из огромного порта, расположенного на геостационарной орбите и
соединённого с Землёй тросами из углеродных нанотрубок. По тросам
ходят лифты, доставляющие людей и грузы на орбиту.
Завтра группа ключевых сотрудников корпорации «Акросс» отправится
в космопорт с секретным идеологическим заданием.
Руководство космопорта выделило для доставки людей на орбиту специальный
двухместный лифт. Глава «Акросса» потребовал, чтобы в любой момент времени
суммарная значимость сотрудников, находящихся в лифте, не превышала некоторой
фиксированной величины. При этом условии даже в случае чрезвычайного
происшествия потеря корпорации не будет невосполнимой.
Сотрудники садятся в лифт в порядке живой очереди. Лифт отправляют наверх, если
в него зашли уже два человека, либо же зашёл один человек, но следующий
за ним слишком значим для корпорации, чтобы их вместе можно было отправить в
одном лифте.
Руководство космопорта хочет узнать максимальное количество рейсов, которое
может потребоваться для перевозки всех сотрудников, чтобы заранее запасти необходимое количество кислородных баллонов и заряженных аккумуляторов.
Исходные данные
В первой строке записаны целые числа n и s — количество сотрудников
«Акросса», отправляющихся на задание, и максимальная суммарная
значимость двух сотрудников, при которой они могут вместе ехать в лифте
(1 ≤ n ≤ 105; 1 ≤ s ≤ 109).
Во второй строке записаны целые числа v1, …, vn — значимости
сотрудников (1 ≤ vi ≤ s).
Результат
В первой строке выведите максимально возможное количество рейсов лифта.
Во второй строке выведите значимости сотрудников в порядке от первого
сотрудника в очереди к последнему, при которых лифт совершит указанное
количество рейсов. Если возможных ответов несколько, выведите любой из них.
Пример
исходные данные | результат |
---|
6 6
1 2 3 3 4 5
| 5
2 5 1 3 4 3
|
Автор задачи: Алексей Самсонов
Источник задачи: XVI Открытый чемпионат Урала по спортивному программированию (апрель, 2012)