S - Súťaž

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Samko cestuje z Bratislavy do Košíc na programátorskú súťaž. Pretože myslí ekologicky, cestuje elektroautom. Jeho auto však nemá dostatočný dojazd, a musí niekoľko krát počas cesty zastaviť a dobiť batériu. Popri jeho ceste je niekoľko nabíjacích staníc - nabíjanie batérie trvá pomerne dlho, takže chce zastavovať čo najmenej.

Úloha

Spočítajte najmenej koľko krát musí elektroauto zastaviť a dobiť batériu počas cesty.

Vstup

Na vstupe sú dve kladné celé čísla 1 ≤ S, D ≤ 3 000 určujúce počet nabíjacích staníc S, dojazd auta D. V ďalšom riadku je S medzerou oddelných vzdialeností, 1 ≤ Vi ≤ 3 000, staníc od cieľovej destinácie. Auto vyráža z prvej stanice, kde má nabitú batériu na maximálnu kapacitu a končí v S-tej stanici, kde už dobíjať auto nemusí, lebo je v cieli.
Môžete predpokladať, že stanice sú uvedené v poradí od najvzdialenejšej až po najbližšiu od cieľa.

Výstup

Výstup obsahuje jeden riadok s jedným celým číslom, minimálny počet zastavení na dobitie auta. V prípade, že sa do cieľa nedá dostať, vypíšte hodnotu -1.

Príklad

Vstup:

10 120
730 680 610 520 410 350 240 120 60 0

Výstup:

UPJŠ ŠVK 2019