2. Zabudnutá chata

Kde bolo tam bolo, tam, kde sa piesok lial a nesypal, kde vtáky spievali pop-punkové balady, v krajine bohatej na prírodu sa nachádzal borovicový les. V strede tohto lesa sa nachádzala zabudnutá chata. Vedúci KSP (kúlový spolok programátorov) sa o tejto chate dozvedeli cez Groogle, ktorý ju označil ako lacnú. Okamžite sa v nej rozhodli spraviť si veľkolepú oslavu, na ktorej sa chce zúčastniť úplne každý.

Ako to však vo svete chodí, nič nie je zadarmo, a aj prenájom tejto chaty niečo stojí. Každý vedúci má našetrenú nejakú sumu peňazí, z ktorej je ochotný prispieť ľubovoľne veľa (ale nie viac). Problém je však v tom, že na chatu chce dať každý presne rovnakú sumu, ako na ňu dajú ostatní¹.

Keďže je táto chata taká zabudnutá, pani domáca nie je veľmi zvyknutá na ľudí a dokáže byť pomerne nevrlá². Vedúci si ju nechcú pohnevať napríklad tým, že jej budú platiť v centoch, a preto radšej každý zaplatí sumu v celých eurách, aj keby mali celkovo zaplatiť viac, ako je potrebné.

Úloha

Pre danú cenu chaty \(c\) a osobné finančné limity každého vedúceho \(s_i\) zistite maximálny počet ľudí, ktorí sa môžu zúčastniť tejto chaty. Dokopy musia byť schopní chatu zaplatiť a každý z nich musí zaplatiť rovnakú celočíselnú sumu (pričom nikto nepresiahne svoj limit). Nezaujíma nás, či za cenu pridania ďalšieho vedúceho zaplatíme dokopy o niečo viac.

Formát vstupu

Na prvom riadku dostanete postupne celé čísla \(n, c\) (\(1 \leq n \leq 150\,000\), \(0 \leq c \leq 10^9\)) – počet vedúcich a cenu chaty. Na nasledujúcom riadku bude \(n\) medzerou oddelených čísiel \(0 \leq s_i \leq 10^9\). \(s_i\) reprezentuje najväčšiu sumu, ktorú je ochotný zaplatiť \(i\)-ty vedúci.

Medzivýpočty sa nemusia zmestiť do klasických celočíselných premenných. Odporúčame preto používať typy long long v C++, prípadne int64 v Pascale.

Formát výstupu

Vypíšte jedno číslo – maximálny počet vedúcich, ktorí sa chaty zúčastnia. Výstup nezabudnite ukončiť znakom nového riadku.

Príklad

Input:

3 47
47 1 42

Output:

2

Zaplatia to prvý vedúci s tretím, každý po 24 eurách.

Input:

10 7
0 1 0 0 2 1 1 1 0 1

Output:

0

Hoci by vedúci vedeli dať dokopy 7 eur, každý musí zaplatiť rovnako veľa. Preto vedúci zaplatiť nevedia a na chatu nepôjde nikto.