Байдарки для команды

После тренировки по гребле команда хочет переправиться на другой берег на учебных байдарках.

Каждая байдарка выдерживает суммарный вес не больше L и в ней могут сидеть не более двух спортсменов. Тренер хочет выдать байдарки так, чтобы байдарок было как можно меньше.

Важно: числа большие (как на олимпиадах), используйте 64-битные целые. В Python это не проблема.

Формат ввода

В первой строке даны два целых числа n и L — число спортсменов и грузоподъёмность байдарки. Во второй строке даны n целых чисел w1, w2, ..., wn — веса спортсменов.

Формат вывода

Выведите одно целое число — минимальное количество байдарок.

Ограничения

• 2 ≤ n ≤ 35000
• 1 ≤ L ≤ 2·10^9
• 1 ≤ wi ≤ 10^9
• Гарантируется, что wi ≤ L для всех i (то есть каждого спортсмена можно посадить хотя бы одного).

Пример

Ввод:

4 10
6 6 4 4

Вывод:

2

Ключевое наблюдение: если в байдарке можно максимум 2 человека, то «самый тяжёлый» спортсмен задаёт почти всё. Ему выгоднее всего искать самого лёгкого напарника: если даже с самым лёгким он не помещается, значит он точно поедет один.

Это и есть жадный выбор: берём самого тяжёлого из оставшихся и пробуем добавить к нему самого лёгкого. Такой шаг не ухудшает ответ, потому что тяжёлого всё равно нужно куда-то посадить, а посадить к нему кого-то тяжелее, чем самый лёгкий, только сложнее.

План решения:

• Считай n, L и массив весов.
• Отсортируй веса по возрастанию.
• Поставь два указателя: i = 0 (самый лёгкий), j = n-1 (самый тяжёлый), ответ boats = 0.
• Пока i <= j:
• Увеличь boats на 1 (мы выделяем одну байдарку под спортсмена j).
• Если i == j — это последний человек, остановись.
• Если w[i] + w[j] <= L, то они едут вместе: сделай i += 1 и j -= 1.
• Иначе тяжёлый едет один: сделай только j -= 1.

Мини-сниппет условия шага: if w[i] + w[j] <= L: i += 1; j -= 1 else: j -= 1

Сложность: сортировка O(n log n), проход двумя указателями O(n).

Частая ошибка: двигать i, когда пара не помещается (нельзя «облегчить» тяжёлого, меняя лёгкого на более тяжёлого). Также не забудь корректно обработать случай i == j.