lac

Petru, un IT-ist pasionat de fotografie, și-a instalat cortul pe malul lacului Colibița din Bistrița-Năsăud. În fiecare dimineață, acesta admiră un peisaj de basm: răsăritul soarelui care oglindește conturul pădurii în apele liniștite.

Pe malul lacului se află $N$ brazi dispuși circular, numerotați de la $1$ la $N$ (bradul $1$ fiind vecin cu bradul $N$). Pentru fiecare brad $i$ se cunoaște:

• înălțimea sa $h_i$
• înălțimea inițială (la momentul de timp $0$) a reflexiei sale în apă $r_i$

unde $1 \leq i \leq N$.

Pe măsură ce timpul trece și soarele urcă pe cer, reflexia $r_i$ a fiecărui brad $i$ $(1 \leq i \leq N)$ scade cu $1$ la fiecare unitate de timp, până când devine $0$. Definim înălțimea observabilă a unui brad $i$ la momentul de timp $t$ ca fiind suma dintre înălțimea sa $h_i$ și înălțimea reflexiei sale în apă la momentul respectiv, adică $H_i(t) = h_i + \max(r_i - t, 0)$.

Să considerăm o secvență formată din $k$ brazi situați pe poziții consecutive (ținând cont de circularitate). Denumim dreptunghi observabil asociat acestei secvențe un dreptunghi de arie maximă care îndeplinește următoarele două condiții:

1. are înălțimea paralelă cu brazii și este înscris în profilul format de înălțimile brazilor (zona 1) și ale reflexiilor acestora (zona 2), unificarea celor două zone realizându-se la nivelul apei (vezi Figura 1);
2. se suprapune atât peste zona 1, cât și peste zona 2, deci înălțimea minimă a reflexiilor brazilor din secvență la momentul de timp respectiv trebuie să fie strict pozitivă.

Aria dreptunghiului observabil este egală cu numărul de brazi din secvență $k$ înmulțit cu înălțimea dreptunghiului la momentul de timp respectiv.

Petru vrea să determine primul moment de timp $t$ (cel mai mic) pentru care există cel puțin o secvență de brazi pentru care dreptunghiul observabil asociat secvenței are aria exact $A$.

Cerință

Scrieți un program care, cunoscând numărul de brazi, valoarea $A$, înălțimile brazilor și ale reflexiilor lor la momentul de timp $0$, determină cel mai mic moment de timp $t$ pentru care există cel puțin o secvență de brazi pentru care dreptunghiul observabil asociat secvenței are aria exact $A$. Dacă nu există un astfel de moment de timp, se va afișa $-1$.

Date de intrare

Fișierul de intrare lac.in conține pe prima linie două numere naturale $N$ și $A$ cu semnificația din enunț. Pe linia a doua din fișier se găsesc $N$ numere naturale ce reprezintă, în ordine, înălțimile celor $N$ brazi. Pe linia a treia se găsesc $N$ numere naturale ce reprezintă, în ordine, înălțimile reflexiilor inițiale a celor $N$ brazi. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire lac.out conține o singură linie pe care este scris un număr natural ce reprezintă răspunsul la cerință.

Restricții și precizări

• $1 \leq N \leq 10^5$
• $1 \leq h_i, r_i \leq 10^6$, pentru $1 \leq i \leq N$
• $1 \leq A \leq 10^9$

Exemplu

lac.in

4 24
7 6 6 7
5 1 5 4

lac.out

2

Explicație

Aria căutată este $A = 24$. Înălțimile inițiale ale brazilor: $7 \ 6 \ 6 \ 7$. Înălțimile reflexiilor inițiale ale brazilor: $5 \ 1 \ 5 \ 4$.

Înălțimile observabile la momentul de timp $t = 0$: $12 \ 7 \ 11 \ 11$.

Pentru secvențele de brazi care se pot forma, ariile dreptunghiurilor observabile sunt: $7$, $11$, $12$, $14$, $20$, $21$, $22$, $28$, $30$.

Înălțimile observabile la momentul de timp $t = 1$: $11 \ 6 \ 10 \ 10$.

Se observă că înălțimea reflexiei bradului $2$ a devenit $0$, deci bradul $2$ nu mai poate fi utilizat în niciun dreptunghi observabil. Pentru secvențele de brazi care se pot forma, ariile dreptunghiurilor observabile sunt: $10$, $11$, $18$, $20$, $27$.

Înălțimile observabile la momentul de timp $t = 2$: $10 \ 6 \ 9 \ 9$.

Pentru secvența circulară formată din brazii $3 \ 4 \ 1$ avem aria dreptunghiului observabil este egală cu $24$.

Deci $t = 2$ este cel mai mic moment de timp pentru care se poate obține această arie.