7. Kto Spasí Pochúťku

Timka je veľká kuchárka a na 40. výročie KSP napiekla tortu. Lenže, naskytol sa problém: Timka by chcela tortu doniesť do T2¹, lenže sa tam sama nevie práve dostať. Chcela by preto tortu poslať do T2 cez iných vedúcich. Problém však je, že keď sa vedúci dostane ku torte, okoštuje ju (“veď to si nikto nevšimne”).

Preto by Timka chcela poslať tortu do T2 cez čo najmenej vedúcich.

Problém však je, že vedúci sú leniví a nechce sa im chodiť ďaleko. Keď si dvaja vedúci idú vymeniť tortu, stretnú sa presne v polceste, – keby jeden musel ísť dlhšie ako druhý, bolo by to nespravodlivé!

Vedúci môžu, ale nemusia byť ochotní sa prejsť trochu dlhšie do T2², podľa toho ako priateľská im práve pripadá.

Pomôžte Timke prepraviť tortu do T2 cez čo najmenej vedúcich!

Úloha

Máme \(N\) vedúcich (Timka je jedna z nich), ktorých si vieme predstaviť, že sa nachádzajú na priamke. Na tej istej priamke sa nachádza aj T2, povedzme, že na pozícii \(0\).

\(i\)-ty vedúci je na prepravu torty ochotný prejsť \(d_i\) metrov.

Navyše, T2 má priateľskosť D.

Torta medzi vedúcimi putuje tak, že vedúci sa vždy stretnú v polceste, torta zmení (dočasného) majiteľa a ten s ňou odkráča späť, odkiaľ prišiel. Dvaja vedúci si tortu vedia vymeniť len vtedy, ak sú obaja ochotní prejsť vzdialenosť do polcesty medzi nimi.

Vedúci sú (niekedy) ochotní prejsť sa viac ako \(d_i\) metrov do T2. Všetko záleží na tom, ako priateľská im T2 práve pripadá. Tento faktor je pre všetkých rovnaký, vyjadrený číslom \(D\). \(i\)-ty vedúci je ochotný zaniesť tortu do T2, ak je od nej vzdialený najviac \(2\min(d_i,D)\) metrov.

Rozhodnite, či vie Timka dostať tortu do T2 a ak áno, koľko najmenej vedúcich musí tortu prenášať.

Formát vstupu

V prvom riadku vstupu sú dve čísla oddelené medzerou: \(N\) (\(1 \leq N \leq 2\times 10^5\)) – počet vedúcich a \(1\leq D \leq 10^8\) – priateľskosť T2.

Na druhom riadku sú medzerami oddelené pozície vedúcich (v metroch), všetky v absolútnej hodnote nepresahujúce \(10^9\). Všetky pozície sú navzájom rôzne a nie sú \(0\).

Na poslednom riadku sú medzerami oddelené \(d_1,\dots, d_N\) – vzdialenosti (v metroch), ktoré sú vedúci ochotní s tortou prejsť. Všetky sú medzi \(1\) a \(10^8\).

Timka je vedúca číslo \(1\) (prvá vedúca uvedená vo vstupe). T2 je na pozícii \(0\).

Úloha má štyri sady. V prvých dvoch platí, že \(N \leq 1000\). Navyše, v tretej sade platí, že vzdialenosti, ktoré sú vedúci ochotní prejsť, sú malé – \(d_i \leq 50\).

Formát výstupu

Ak Timka nevie dostať tortu do T2, vypíšte “Torta nebude”.

Inak, vypíšte jedno celé číslo: koľko najmenej vedúcich (vrátane Timky) treba, aby sa torta dostala do T2?

Príklady

Input:

9 1
14 -2 2 4 6 8 10 12 16
1 5 1 1 1 5 1 1 4

Output:

4

Timka vie najlepšie tortu poslať deviatemu vedúcemu (do polcesty to majú obaja \(1\) meter). Ten by mal poslať tortu vedúcej na pozícii 8 (do polcesty to majú obaja \(4\) metre). Tá ju ešte nevie poslať sama do T2 (do T2 sa tu nikomu nechce, pokiaľ nie je ozaj blízko), tak pošle tortu vedúcemu na pozícii \(-2\), ktorý ju už do T2 vie doniesť. Torta prejde cez \(4\) vedúcich (vrátane Timky)

Input:

2 5
5 100
2 2

Output:

Torta nebude

V tomto prípade je T2 pre Timku prílíš ďaleko, lenže jediná ďalšia vedúca je ešte ďalej.