Serban si Kendama

Șerban este pasionat de kendama. De câțiva ani, și-a deschis o mică afacere în care montează ațe noi pentru kendama. În fiecare săptămână, primește mai multe role de ață — unele mai lungi, altele mai scurte — și trebuie să le taie în bucăți egale pentru clienți.

Într-o zi, Șerban a primit o comandă specială: trebuie să pregătească cel puțin $K$ bucăți de ață, toate de aceeași lungime $L$, pentru un club de kendama care organizează un concurs.

Fiecare rolă de ață are o anumită lungime, exprimată printr-un număr natural nenul de unități. Dintr-o rolă poate obține mai multe bucăți de lungime $L$, dar nu are voie să lipească resturile între ele pentru a face o bucată mai lungă.

Șerban vrea să fie eficient: dorește să aleagă cea mai mare lungime $L$ astfel încât să poată tăia cel puțin $K$ bucăți egale din toate rolele sale.

Ajută-l pe Șerban să afle lungimea maximă posibilă a bucăților de ață pe care o poate obține.

Cerință

Șerban are $N$ ațe, ața $i$ are lungimea $A[i]$. Vrea să taie ațele să obțină cel puțin $K$ bucăți de aceeași lungime $L$. Din fiecare ață poate obține mai multe bucăți.

Determinați lungimea maximă $L$ pentru care este posibil ca Șerban să obțină cel puțin $K$ bucăți.

Date de intrare

Fișierul de intrare kendama.in conține:

• pe prima linie două numere naturale nenule, $N$ și $K$, cu semnificația din enunț;
• pe următoarea linie $N$ numere naturale nenule, reprezentând elementele șirului $A$.

Date de ieșire

Se va afișa în fișierul de ieșire kendama.out lungimea maximă $L$ care se poate obține, iar în cazul în care nu se pot tăia cel puțin $K$ bucăți de aceeași lungime se va afișa valoarea $0$.

Restricții și precizări

• $1\leq N\leq 200 \ 000$;
• $1\leq A[i]\leq 10^{9}$, $1\leq i\leq N$;
• $1\leq K\leq 10^{12}$.

Exemplu 1

kendama.in

7 8
6 3 1 4 2 5 1

kendama.out

2

Explicație

Șerban poate obține $(3,1,0,2,1,2,0)$ bucăți de la fiecare ață. $3+1+0+2+1+2=9$, iar $8\leq9$. Orice $L$ mai mare ca 2 nu ar satisface condiția.

Exemplu 2

kendama.in

5 11
802 743 457 539 1000

kendama.out

267