2. Repa reparuje

Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Merlinovi na [email protected] alebo Matejovi na [email protected].

Začala sa karanténa a dedko Repa má kopu voľného času. Rozhodol sa s ním preto spraviť niečo produktívne. Zrenovuje svoju záhradku! Teda presnejšie už konečne vymení dlaždice na tom porozbíjanom chodníku. Nevie si ale vybrať, ktoré dlaždice má kúpiť. Pomôžte mu.

Úloha

Chodník, ktorý chce dedko vydláždiť má dĺžku \(d\). Na výber má z \(n\) typov kachličiek, z ktorých \(i\)-ty má dĺžku \(l_i\). Vašou úlohou je nájsť taký typ kachličiek, ktorého keď kúpi ľubovoľne veľa, tak dokáže vydláždiť celý chodník bez toho aby musel rezať kachličky. Ak sa to dá dosiahnuť viacerými typmi kachličiek, nájdite taký typ, z ktorého treba kúpiť najmenej kusov.

Formát vstupu

Na prvom riadku vstupu sú čísla \(1 \leq n \leq 10^6\) a \(1 \leq d \leq 10^8\), počet typov kachličiek a dĺžka chodníka, ktorý chce dedko vydláždiť. V druhom riadku nasleduje \(n\) čísel. Číslo \(l_i\) (\(1 \leq l_i \leq 10^8\)) je dĺžka \(i\)-teho typu kachličky.

Formát výstupu

Vypíšte jedno číslo, najmenší možný počet kachličiek, ktorý musí dedko nakúpiť aby vydláždil svoj chodník. Ak to nedokáže žiadnym typom kachličky bez rezania, vypíšte \(-1\).

Hodnotenie

Existuje 5 sád vstupov. Pre prvú sadu navyše platí, že \(n,d \leq 100\). Pre druhú a tretiu sadu platí, že \(n \leq 10^4\). Pre posledné dve sady neplatia žiadne ďalšie obmedzenia.

Príklad

Input:

5 12
3 8 4 6 1 

Output:

2

Kachličiek prvého typu by sme potrebovali 4 kusy, druhým typom sa chodník bez rezania vydláždiť nedá, z tretieho potrebujeme 3 kusy, zo štvrtého 2 kusy a z posledného 12. Teda potrebujeme kúpiť najmenej 2 kusy kachličiek.

Input:

3 7
2 3 4

Output:

-1