Rezolvare PBinfo #3406

Cerința

Fie N un număr întreg impar și un vector A cu N elemente. Pentru fiecare element Ai, acesta se poate incrementa cu 1. Fiecare element sepoate incrementa cel mult odată. Mai mult, se pot realiza cel mult K incrementări.

Scopul este de a maximiza medianul lui A. Medianul unui vector este definit ca fiind elementul din mijlocul vectorului după sortarea acestuia. De exemplu, medianul vectorului [5,8,2,9,1] este 5.

Date de intrare

Prima linie conține un număr impar N și un întreg K. Pe a doua linie se află N numere separate prin spații naturale, reprezentând elementele vectorului.

Date de ieșire

Programul va afișa pe ecran numărul ce reprezintă maximul posibil al medianului după aplicarea operațiilor de incrementare.

Restricții și precizări

• 1 ≤ k ≤ n ≤ 1000, N e impar.
• 1 ≤ Ai ≤ 1000.

Exemplu:

Intrare

9 3
4 4 4 8 2 2 9 9 1

Ieșire

5

Explicație

Se pot incrementa elementele de pe pozițiile 1, 2 și 3. Valoarea comună reprezintă medianul maxim care se poate obține.