В ряд стоят N звуковых мониторов. Их исходные громкости уже упорядочены: a₁ ≤ a₂ ≤ … ≤ aₙ. N чётно. За действие можно выбрать ровно N/2 подряд идущих мониторов и увеличить громкость каждого на 1. Разрешено не более K действий. Найдите наибольшую достижимую минимальную громкость среди всех мониторов.
Формат ввода
В первой строке N, во второй K, затем N чисел aᵢ, каждое на отдельной строке. 2 ≤ N ≤ 10^5, N чётно; 1 ≤ K ≤ 10^9; 1 ≤ aᵢ ≤ 10^9; a₁ ≤ … ≤ aₙ.
Формат вывода
Выведите одно целое число — ответ на задачу.
Примеры
ввод
4 3 1 2 4 5
вывод
4
Войдите, чтобы отправлять решения.