2. Obávaná skratka

Čo by to bolo za hry v Koloseu, keby sa ich nezúčastnili aj Galovia? Emanix¹ sa rozhodol zúčastniť sa na gladiátorských súbojoch. Na chrbát si pripol svoju obľúbenú zbraň², do ruky zobral štít³ a so svojím druidom Prefixom sa vydal na cestu. Pred cestou sa, samozrejme, poriadne najedol – presne tak, ako sa na Gala patrí.

Cesta bola plná nástrah, preto sa Emanix musel pohybovať rýchlo. Po namáhavom dni sa dostali na rázcestie. Tam Prefix zazrel tabuľu, ktorá hovorila o úžasnej skratke ku Koloseu, ktorá vedie cez záhradky Rímskeho impéria. Čo však je horšie, miestni majú už plné zuby Galov, čo si tadiaľ skracujú cestu. Preto v momente, ako naši dvaja hrdinovia vkročia do nejakej záhradky, rozbehne sa za nimi strážny diviak. Ako správny projekt Rímskeho imperiálneho fondu regionálneho rozvoja má každá záhrada na začiatku tabuľku, na ktorej je napísané, za aký čas diviak votrelca v tejto záhradke chytí. Akonáhle votrelec opustí záhradku, diviak ho prestane prenasledovať (nejedná sa už o jeho územie, tak prečo by sa mal namáhať?).

Keďže bol Emanix po celom dni unavený⁴, pohyboval sa konštantnou rýchlosťou \(0.5\, m/s\). Prefix sa ako verný pomocník ponúkol, že Emanixovi pomôže odniesť zbroj. Emanix ako silný emancipovaný Gal však odmietol. Namiesto toho sa rozhodol, že pokiaľ nebude stíhať ujsť pred diviakom, napije sa zo svojho čarovného nápoja, ktorý zvýši jeho rýchlosť dvojnásobne. Čarovný nápoj však účinkuje iba \(k\) sekúnd a Prefix ako skúsený druid neodporúča užívať viac dávok naraz – môže to mať veľmi nepriaznivé účinky na Emanixov metabolizmus. Hneď ako účinok nápoja vyprchá, Emanix si môže dať ďalší dúšok.

Emanix je teraz zvedavý, či sa dokáže dostať touto cestou až do Kolosea. Pomôžte mu zistiť, či dokáže prejsť cez všetky záhradky bez toho, aby ho dobehol nejaký diviak. Ak to Emanix dokáže, zistite, koľkokrát sa musí napiť zo svojho čarovného nápoja.

Úloha

Na ceste sa nachádza \(n\) záhradiek tesne za sebou (tam, kde jedna záhradka končí, ďalšia začína). Vašou úlohou je zistiť, či sú Emanix s Prefixom schopní dostať sa cez všetky záhradky bez toho, aby ich ktorýkoľvek diviak dohnal. Ak to dokážu, musíte tiež zistiť, koľko najmenej krát sa musí Emanix napiť zo svojho čarovného nápoja. O každej záhradke viete jej dĺžku \(l\) a čas \(t\) – najdlhší čas, ktorý môže byť Emanix v danej záhradke (ak by tam bol dlhšie, dobehol by ho diviak).

Formát vstupu

Na prvom riadku vstupu sa nachádzajú dve čísla \(n\) a \(k\) (\(1 \leq n \leq 5 \cdot 10^5\), \(1 \leq k \leq 10^{12}\)). \(n\) je počet záhradiek, \(k\) je trvanie účinku čarovného nápoja v sekundách. Na druhom riadku sa nachádzádza postupnosť medzerami oddelených čísiel \(l_1, l_2, \dots, l_n\) (\(1 \leq l_i \leq 10^6\)), ktoré označujú dĺžky jednotlivých záhradiek v metroch. Na posledom riadku sa nachádza postupnosť medzerami oddelených čísiel \(t_1, t_2, \dots, t_n\) (\(1 \leq t_i \leq 10^7\)) - časy, za ktoré Emanixa a Prefixa v jednotlivých záhradkách dobehne diviak, v sekundách.

Formát výstupu

Na výstup vypíšte, najmenej koľkokrát sa bude musieť Emanix napiť čarovného nápoja, aby cez záhradky stihli prejsť. Ak Emanix nedokáže cez záhradky prejsť, vypíšte \(-1\).

Príklady

Input:

1 3
7
10

Output:

2

Emanix sa môže napiť napríklad hneď na začiatku. Za prvé \(3\) sekundy prejde \(3\) metre. Potom sa napije znovu a za ďalšie \(3\) sekundy prejde ďalšie \(3\) metre. Potom nápoj prestane účinkovať a posledný meter teda Emanixovi bude trvať \(2\) sekundy. Ak by sa napil iba raz, počas trojsekundového účinku nápoja by stihol prejsť \(3\) metre a na zvyšné \(4\) by potreboval \(8\) sekúnd, čo je dokopy viac než povolených \(10\) sekúnd.

Input:

3 100000
5 5 5
5 7 8

Output:

1

Input:

4 1000
1 2 3 4
10 9 10 9

Output:

0

Input:

3 3
3 3 3
3 3 2

Output:

-1

Cez poslednú záhradku Emanix nestihne prejsť, ani keby bol celý čas pod účinkom nápoja.