Crama

Șeful Șefilor a reușit, după ce a câștigat la "Romanian Trick" (Rămâne de văzut dacă voi l-ați ajutat sau dacă a trebuit să-i convinga pe domnii polițiști în legătura cu scopul călătoriei sale, iar aceștia, din milă, l-au lăsat să câștige). Acum, odată ce a trecut prutul, șeful merge direct la o faimoasă cramă, ce produce anual milioane de sticle de vin de colecție ce sunt vândute în întreaga lume.

Șeful învață de la ghidul turistic din cadrul excursiei din care face parte că sticlele de vin trec printr-un proces de "Transformare Spumantă", ce constă în schimbarea numărului de pe eticheta unei sticle de vin în numărul respectiv scris în baza doi. Acest număr este mai departe tratat ca fiind un număr natural, din baza 10, chiar dacă a fost format prin transformarea în baza doi a numărului original.
Exemplu: numărul $71$ devine $1000111$ (un milion o sută unsprezece).

După ce vizitează galeriile subterane imense ale acestei crame, șeful se îndreaptă spre magazin, unde este provocat la un meci de "Moldovan Trick" de către vânzător, cu miza de a câștiga o sticlă de vin de excepție. Astfel, jocul se derulează astfel și sunt două moduri de a îl juca:

1. "Moldovan Trick" cu vin alb - Șefului îi sunt oferite $N$ sticle de vin alb, așezate pe un rând, pe o masă din lemn de stejar. Fiecare sticlă de vin alb are pe eticheta sa un număr. Fiecare sticlă (adica fiecare element din șir) dintre cele $N$ trece prin procesul de Transformare Spumantă descris mai sus. Șeful trebuie să determine numărul maxim ce se află pe eticheta uneia din cele $N$ sticle, după terminarea procesului de Transformare Spumantă.
2. "Moldovan Trick" cu vin roșu - Șefului îi sunt oferite $N$ sticle de vin roșu, așezate pe un rând, pe o masă din lemn de stejar. Fiecare sticlă de vin roșu are pe eticheta sa un număr. Șefului îi mai este oferit și un număr natural $K$. Șeful trebuie să determine care este lungimea minimă a unei subsecvențe continue din șirul dat cu proprietatea că, prin transformarea tuturor sticlelor din interiorul secvenței selectate prin procesul de Transformare Spumantă (adică a numerelor din secvența din șir), șirul rezultat va avea suma $\textbf{totală}$ mai mare sau egală decât $K$. $\textbf{Atenție!}$ În cazul în care este imposibil ca, orice secvență continuă de numere din șir am lua, suma întregului șir să fie mai mare sau egală decât $K$, se va afișa $-1$. Vânzătorul ne garantează nouă și șefului că nu își bate joc de noi și că suma inițială a numerelor de pe etichetele sticlelor nu este mai mare sau egală decât $K$.

Cerință

Dacă se joacă "Moldovan Trick" cu vin alb, să se afișeze numărul maxim ce se află pe eticheta uneia din cele $N$ sticle, după terminarea procesului de Transformare Spumantă.
Dacă se joacă "Moldovan Trick" cu vin roșu, să se afișeze lungimea minimă a unei subsecvențe continue din șirul dat cu proprietatea că, prin transformarea tuturor sticlelor din interiorul secvenței selectate prin procesul de Transformare Spumantă (adică a numerelor din șirul dat), șirul rezultat va avea suma totală mai mare sau egală decât $K$.

Date de intrare

Pe prima linie a fișierului de intrare crama.in se găsesc două numere naturale, $C$ și $N$, ce reprezintă jocul ce se joacă (dacă $C = 1$, se joacă "Moldovan Trick" cu vin alb, dacă $C = 2$, se joacă "Moldovan Trick" cu vin roșu), precum și numărul de sticle ce sunt aduse în fața șefului.
Pe a doua linie a fișierului de intrare se găsesc $N$ numere naturale, reprezentând numerele de pe etichetele sticlelor de vin.
Doar în cazul în care $C = 2$, va mai exista și a treia linie a fișierului de intrare, pe care se va găsi un numar natural $K$, cu semnificația din enunț.

Date de ieșire

Pe prima linie a fișierului de ieșire crama.out se va găsi un singur număr întreg, răspunsul din cadrul jocului jucat.

Restricții și precizări

• $1 \leq C \leq 2$;
• $1 \leq N \leq 500 \ 000$
• $0 \leq$ Numărul scris pe eticheta unei sticle de vin $\leq 4096$
• $0 \leq K \leq 1 \ 000 \ 000 \ 000 \ 000 \ 000 \ 000$, $K$ va exista în fișierul de intrare doar dacă $C = 2$.

  #	Punctaj	Restricții
  0	0	Exemple
  1	30	$C = 1$, adică se joacă "Moldovan Trick" cu vin alb.
  2	30	$C = 2$, $N \le 1000$
  3	40	$C = 2$, fără restricții suplimentare.

Exemplul 1

crama.in

1 5
71 32 128 131 1

crama.out

10000011

Explicație

$71$ devine, după Transformarea Spumantă, $1000111$.
$32$ devine, după Transformarea Spumantă, $100000$.
$128$ devine, după Transformarea Spumantă, $10000000$.
$131$ devine, după Transformarea Spumantă, $10000011$.
$1$ devine, după Transformarea Spumantă, $1$.

Observăm că cel mai mare număr dintre acestea obținute este $10000011$.

Exemplul 2

crama.in

2 4
3 5 7 1
210

crama.out

2

Explicație

Inițial, suma numerelor de pe etichete este egală cu $16$. Dacă aplicăm operația de Transformare Spumantă asupra subsecvenței continue $5, 7$ de lungime $2$, obținem șirul:
$3, 101, 111, 1$. Astfel, suma șirului devine 216, sumă ce este mai mare sau egală decât $K$, care este egal cu $210$.
Se poate demonstra că nu putem ajunge la o sumă mai mare sau egală decât $210$ aplicând operația de Transformare Spumantă asupra unei subsecvențe continue de lungime mai mică decât $2$, deci răspunsul este chiar $2$.