Î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;
- nici un 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, c1, c2, ... cn separate prin câte un spaţiu. Valoarea ci 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
2 <= n, p <= 50000
1 <= c1, c2, ... cn <= 50000
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 pe nici un test 2 000 000 000
Exemple
tabara.in
tabara.out
Explicaţii
2 2
1 3
3
Codificând cele două regiuni cu x şi y, se pot completa maxim 3 cabane în felul următor: [x1,y1], [p1,y2], [p2,y3] .
x1 reprezintă singurul copil din regiunea 1, y1,y2,y3 reprezintă cei trei copii din regiunea 2, iar p1,p2 sunt cei doi profesori.
3 4
2 3 4
4
Dacă cele 3 regiuni sunt x, y, z, atunci se pot completa 4 cabane în felul următor:
[x1,y1,z1], [x2,p1,z2], [p2,y2,z3], [p3,y3,z4]
x1,x2 identifică cei doi copii din regiunea 1, etc. Profesorul p4 nu va fi cazat.