Кожна школа отримує або нуль, або рівно ланч-боксів, тому задача така: вибрати якнайбільше чисел k_i так, щоб їхня сума не перевищувала .
Тут працює проста жадібність: щоб взяти якнайбільше замовлень, вигідно починати з найменших.
Формально: нехай в оптимальному наборі з шкіл є якась школа, а поза набором — школа з меншим (або рівним) замовленням. Замінивши першу на другу, ми не збільшимо суму й не змінимо кількість шкіл. Повторюючи такі заміни, приходимо до набору з найменших замовлень. Отже, якщо взагалі можливо обслужити шкіл, то можливо обслужити саме найменших.
Розв'язок: відсортувати масив за зростанням, накопичувати префіксну суму й рахувати, скільки замовлень встигли додати, доки сума не перевищила . Щойно чергове додавання виводить суму за межу — зупиняємось і виводимо лічильник.
Складність — \mathcal{O}(M \log M) через сортування. Суму накопичуйте у 64-бітному типі, бо вона може помітно перевищити ще до зупинки.