Problem 3927: Primarie

Primăria orașului Orăștie a accesat fonduri europene in valoare de $X$ milioane de euro. Primarul, Bogdan, își dorește reorganizarea intregului oraș în cartiere, unde fondurile vor fi împărțite ulterior. În oraș, sunt $N$ locuințe numerotate de la $1$ la $N$ , dispuse de la stânga către dreapta, fiecare locuință având un grad de frumusețe. Frumusețea unui cartier este definită ca suma frumuseților clădirilor componente. Primarul știe că anumite cartiere vor avea un grad de frumusețe mai mic decât altele, însă nu dorește ca diferența dintre cel mai frumos cartier și cel mai puțin frumos cartier sa fie mai mare decât $X$ , întrucât asta îl va obliga să plătească mai mult decât bugetul alocat pentru a egala cartierele. Astfel, împarte orașul în cartiere de câte $K$ locuințe consecutive, iar în cazul în care numărul de locuințe nu este divizibil cu $K$ , ultimele $N%K$ locuințe formează propriul cartier. Astfel, pentru $N = 8, \ K = 3$ , cartierele vor fi $[1,2,3], \ [4,5,6], \ [7,8]$

Cerință

Dându-se $N$ , numărul de locuințe, $X$ cantitatea de fonduri europene accesate și frumusețile clădirilor, să se determine valoarea maxima $K$ pentru care diferența dintre cel mai frumos și cel mai puțin frumos cartier să nu depășească $X$ .

Date de intrare

Pe prima linie se găsesc numerele naturale $N$ și $X$ .
Pe a doua linie se găsesc $N$ numere întregi, reprezentând frumusețea fiecărei clădiri.

Date de ieșire

Se va afișa pe prima linie un singur număr — valoarea maximă a lui $K$ pentru care diferența maxima dintre frumusețile a două cartiere să fie $\leq X$

Restricții

$1 \leq N \leq 1{,}000{,}000$
$1 \leq X \leq 10^{18}$
Toate rezultatele intermediare se vor încadra pe 64 de biți

Subtask-uri:

Pentru 30 de puncte $1 \leq N \leq 2000$
Pentru 70 de puncte Fără alte restricții.

Exemple

Exemplul 1

stdin

5 30
-3 1 -9 -2 10

stdout

Explicație

Putem forma un cartier din primele 4 clădiri și un cartier din a 5-a clădire. Diferența maximă este $10 - (-3 + 1 - 9 - 2) = 23 \leq 30$

Exemplul 2