Fight Club
Турнир за Купата на Декана, 2011
Time Limit: 0.1s, Memory Limit: 64MiB
Ели е възхитена от физиците в съседния факултет. Те не просто са си построили роботи, ами запълват свободното си време като ги сбиват. Всеки робот има уникална характеристика "сила", която определя колко добре се справя в битките.

Сега те организират турнир. Всеки включил се в него физик има максимум два мача със своя робот – един, в който предизвиква (той избира срещу кого ще се бие), ако има кого да предизвика, и един, в който е предизвикан (някой друг избира да се бие срещу него). Когато някой предизвиква, той избира по-слаб робот, за да може да победи (или не предизвиква никого, ако е най-слабият робот в турнира). Разбира се, мач, в който единият робот просто замахва и превръща противника си в скачащи пружинки, разлято машинно масло и търкалящи се по пода болтове, не е особено интересен. Затова, с цел да са по-равностойни мачовете, предизвикващият винаги избира най-силния робот, който все пак е по-слаб от неговия собствен.

След всеки мач собствениците на роботите трябва да ги поправят, за което трябват ресурси. Нужните пари за поправка след мач между роботи със сила Si и сила Sj са |Si - Sj|. Факултетът има лимит от M лева, които може да изразходва. Физиците се питат колко най-много от записалите се робота могат да участват в турнира, така че сумата от парите за ремонт да са по-малко или равни на M.
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и M – съответно броят роботи, записани за турнира, и с колко пари за ремонти разполагат физиците. На втория ред ще има N цели числа S1, S2, ..., SN – силата на всеки от роботите. Гаранирано е, че няма да има два робота с еднаква сила.
Изход
На стандартния изход изведете едно цяло число - най-големия брой роботи, които могат да участват в турнира.
Ограничения
  • 1 ≤ N ≤ 100,000
  • 1 ≤ М ≤ 1,000,000
  • 1 ≤ SiSj ≤ 1,000,000
Примерен Вход Примерен Изход
5 3 4 6 2 3 9 3
10 7 11 5 13 17 1 4 8 14 9 7 6
В първия пример една от възможните конфигурации роботи са тези със сила 4, 2 и 3. Ще има две битки, едната между този със сила 4 и този със сила 3, и една между този със сила 3 и този със сила 2. Общата цена за поправка е 2. Във втория пример една възможност е да участват роботите със сила 11, 5, 4, 8, 9 и 7.
Мрън!