tabara

Într-o tabară la munte s-au întâlnit copii veniţi din $n$ regiuni diferite ale ţării. Tabara are în dotare suficiente cabane identice cu câte $n$ paturi. Directorul taberei a stabilit, pentru o cât mai bună socializare, următoarele reguli:

• în fiecare cabană trebuie să fie cazate exact $n$ persoane, dintre care cel puţin $n-1$ trebuie să fie copii şi cel mult un profesor;
• copiii cazaţi în fiecare cabană trebuie sa provină din regiuni diferite ale ţării;
• niciun copil sau profesor nu poate fi cazat în mai multe cabane.

Cerinţă

Să se găsească numărul maxim $M$ de cabane care pot fi completate respectând restricţiile de mai sus.

Date de intrare

Fişierul de intrare tabara.in conţine pe prima linie două numere naturale $n$ şi $p$, unde $n$ este numărul de regiuni, iar $p$ este numărul de profesori. Pe linia a doua se găsesc $n$ numere naturale $c_1$, $c_2$, $\dots$, $c_n$ separate prin câte un spaţiu. Valoarea $c_i$ reprezintă numărul copiilor veniţi din regiunea $i$.

Date de ieșire

În fişierul de ieşire tabara.out se va scrie pe prima linie numărul natural $M$.

Restricții și precizări

• $2 \leq n, p \leq 50 \ 000$
• $1 \leq c_1, c_2, ..., c_n \leq 50 \ 000$
• Este posibil ca după completarea celor $M$ cabane, nu toţi elevii şi/sau profesorii să fie cazaţi.
• Numărul total de persoane care trebuie cazate nu va depăşi niciodată $2 \ 000 \ 000 \ 000$.

Exemplul 1

tabara.in

2 2
1 3

tabara.out

3

Explicație

Codificând cele două regiuni cu $x$ şi $y$, se pot completa maxim $3$ cabane în felul următor: $[x_1, y_1]$, $[p_1, y_2]$, $[p_2, y_3]$.

$x_1$ reprezintă singurul copil din regiunea $1$. $y_1$, $y_2$, $y_3$ reprezintă cei trei copii din regiunea $2$, iar $p_1$, $p_2$ sunt cei doi profesori.

Exemplul 2

tabara.in

3 4
2 3 4

tabara.out

4

Explicație

Dacă cele $3$ regiuni sunt $x$, $y$, $z$, atunci se pot completa $4$ cabane în felul următor: $[x_1, y_1, z_1]$, $[x_2, p_1, z_2]$, $[p_2, y_2, z_3]$, $[p_3, y_3, z_4]$.

$x_1$, $x_2$ reprezintă cei doi copii din regiunea $1$, etc. Profesorul $p_4$ nu va fi cazat.