Служба доставки
Ограничение времени 1 секунда
Ограничение памяти 64.0 Мб
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
На Марс заброшена партия стационарных роботов-исследователей. Марсоход должен перевезти их на определённые точки планеты.
Для перевозки роботов есть неограниченное количество транспортных платформ, каждая из которых способна выдерживать определённый вес limit. На одной платформе можно перевезти либо одного робота, либо двух — при условии, что их совокупный вес не превышает limit. Роботы имеют разный вес.
Программа должна получить на вход массив, каждый элемент которого — это вес робота. Второй параметр, который должна принять программа, — это значение limit, грузоподъёмность одной платформы.
Определите минимальное количество транспортных платформ, необходимое для перевозки всех роботов, описанных в массиве.
Количество платформ неограниченно. Каждая платформа выдерживает максимальный вес limit. На каждой платформе можно перевезти не более двух роботов при условии, что их совокупный вес не превышает limit. Вес отдельного робота не может превышать limit. Не забудьте добавить в код аннотации типов данных.
После успешного прохождения тестов на платформе Яндекс Контест отправьте решение на проверку ревьюеру.
Формат ввода
В первой строке записан массив целых чисел, через пробел — это вес отдельных роботов.
Во второй строке записан лимит — предельная грузоподъёмность платформы.
Формат вывода
Целое число, указывающее на необходимое количество платформ для транспортировки.
Пример 1
Ввод
1 2
3
Вывод
1
Пример 2
Ввод
3 2 2 1
3
Вывод
3
Пример 3
Ввод
3 5 3 4
5
Вывод
4