Время

15:33:54
24 May 2012
Версия для печати

Вода

   Недавно  Сергей  пошел  к  колодцу  за  водой,  но  так  и  не  вернулся.  Он  взял  с  собой n канистр, каждую  из  которых  он  полностью  наполнил  водой.  Теперь  Сергей  хочет  доставить  их  в  свой  загородный  дом.  Вот  в  этом  и  заключается  проблема.  За  один  раз  Сергей  может  унести  не  более  2 канистр — у него ведь всего две руки. Более того, он может нести не более k литров воды.

   Теперь Сергей стоит у колодца и думает, за какое минимальное число раз он может отнести всю воду домой, и может ли вообще. Помогите ему решить эту задачу.


Технические условия

   Входные данные

   В первой строке входного файла два целых числа — n и k (1n105). Во второй строке n целых чисел  —  объемы  канистр  в  литрах.  Все  числа  во  входном  файле  положительные  и  не  превышают 109.

   Выходные данные

   Если  Сергей  не  сможет  унести  всю  воду  домой,  выведите  «Impossible».  Иначе  выведите  одно число — минимальное необходимое число раз.


Информация о задаче

Лимит времени: 2 секунды
Лимит памяти: 64 MB
Баллы за пройденный тест: 3.7037
Сложность: 44% 70/126
Классификация: Жадный алгоритм

Пример

Пример входных данных

Sample 1
4 4
1 2 3 3

Sample 2
4 2
1 2 3 3

Пример выходных данных

Sample 1
3

Sample 2
Impossible


← Герой гитары Список задач Древняя рукопись →