Эвакуационные грузовики
После перевозки нескольких неисправных автомобилей из далёкой страны на пароме, они прибыли в соседний город. Теперь их необходимо доставить в столицу. Поскольку автомобили сломаны, единственный способ их транспортировки — это эвакуационные грузовики.
Известно, что два автомобиля можно поместить в один эвакуационный грузовик, если их суммарный вес не превышает определённый порог. Если же их общий вес оказывается больше этого порога, то для каждого автомобиля потребуется отдельный эвакуационный грузовик.
Вам даны
n автомобилей вместе с их весами, а также порог, который может выдержать один эвакуационный грузовик. Требуется определить минимальное количество эвакуационных грузовиков, чтобы перевезти все автомобили.Ввод
В первой строке содержатся два целых числа
n (2 ≤ n ≤ ) и t (1 ≤ t ≤ ) — число автомобилей и максимально допустимый суммарный вес для эвакуационного грузовика.В следующей строке указаны
n целых чисел, разделённых пробелами: (1 ≤ ≤ t), которые представляют веса автомобилей.Вывод
Выведите минимальное количество эвакуационных грузовиков, необходимых для перевозки всех автомобилей.
Примеры
Ввод | Вывод |
4 11
5 8 10 2 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB