Tagy: binárne vyhľadávanie
Obtiažnosť: easy

Rozdávanie cukríkov

Prišiel Mikuláš a priniesol vám veľa cukríkov. A teraz ich chce všetky rozdať. Nie všetci si však zaslúžite rovnako veľa cukríkov. Mikuláš o každom vie, koľko najviac cukríkov si zaslúži a určite mu nikdy nedá viac, aj keď môže dať menej. Chcel by však byť spravodlivý a rozdať cukríky čo najrovnomernejšie. Vo vlastnom záujme mu pomôžte.

Úloha

Na vstupe dostanete počet cukríkov, ktoré chce Mikuláš rozdať a taktiež čísla aia_i určujúce, že človek ii si nezaslúži viac ako aia_i cukríkov. Nájdite najmenšie xx také, že Mikuláš dokáže rozdať všetky cukríky tak, aby nikto nedostal viac ako xx cukríkov.

Vstup

Na prvom riadku sú čísla nn a p(1n1000,1p109)p \, (1 \leq n \leq 1\,000, 1 \leq p \leq 10^9) - počet ľudí, ktorým chce Mikuláš cukríky rozdať a celkový počet cukríkov.

Nasleduje nn čísel ai(1ai106)a_i \, (1 \leq a_i \leq 10^6) - maximálny počet cukríkov, ktoré si zaslúži ii-ty človek.

Výstup

Vypíšte najmenšie xx také, že Mikuláš vie rozdať všetky cukríky a nikto nedostane viac ako xx cukríkov. Ak také xx neexistuje, vypíšte Nic nedostanete.

Príklady

Vstup

Výstup

5 34
9 8 9 9 4
8

Prvým dvom dá Mikuláš 8 cukríkov, ďalším dvom len 7 a poslednému 4, lebo si viac nezaslúži. Takto rozdá všetkých 34 cukríkov. Všimnite si, že ak by chcel dať najviac 7 cukríkov, tak ich rozdá len 32, čo je málo.

Vstup

Výstup

3 7
1 1 4
Nic nedostanete

Aj keby dal každému plný počet cukríkov, rozdá ich len 6.

Ak chceš riešiť túto úlohu, musíš sa najprv prihlásiť.