Ssssss
Национална Студентска Олимпиада 2013
Time Limit: 0.2s, Memory Limit: 64MiB
Ели не обича змии. Всъщност ги мрази. Но с повод и без повод нейните познати ѝ подаряват такива. Момичето подозира, че се опитват да й намекнат нещо.

Змиите са ужасни животни и биха ви нападнали без да им мигне окото (отчасти защото нямат клепачи и не могат да мигат) ако ги настъпите. Нещо повече, те биха нападнали и всяко друго нещо, което застане върху тях – включително друга змия.

Ели има дълъг, но тесен терариум с дължина L, като вече са й подарили N змии с дължини A1, A2, ..., AN. Тъй като терариумът е твърде тесен, във всяка негова част може да лежи най-много една змия, без да застъпва никоя друга (за да не се нападат). Ели има план как да оправдае изхвърлянето на известен брой от змиите! Тя планира да ги постави в терариума по такъв начин, че:
  1. Никоя да не застъпва никоя друга (възможно е обаче да се допират);
  2. Да не може да се сложи нито една от другите змии, без да се наруши правило 1.
Очевидно, змиите не могат да излизат от двете страни на терариума, но могат да се докосват до стените му. Считаме, че змиите не се движат, като могат да бъдат разполагани в произволни участъци на терариума – включително такива с нецелочислени координати!

Казано на по-човешки език, тя трябва да разположи подмножество от N отсечки с дължини A1, A2, ..., AN върху отсечка с дължина L, така че никои две да не се застъпват, и никоя от оставащите да не може да бъде сложена изцяло в непокритите интервали.

Помогнете на Ели да намери максималния брой змии, чието изхвърляне може да оправдае ако разположи останалите оптимално.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и L – съответно броя змии и дължината на терариума. Вторият от тях съдържа N числа A1, A2, ..., AN – дължините на всяка от змиите.
Изход
На стандартния изход изведете по едно единствено цяло число – максималния брой змии, които Ели може да изхвърли.
Ограничения
  • 1 ≤ N ≤ 30
  • 1 ≤ L ≤ 1000
  • 1 ≤ Ai ≤ 100
Примерен Вход Примерен Изход
2 9 1 8 1
5 36 1 5 1 5 5 1
6 18 2 10 2 9 9 2 4
Ето едно възможно разпределение във втория пример:
Ssssss Example
Мрън!