e-olymp

Transit

Країна Ужляндія має вигідне географічне розташування – її територія знаходиться на перетині важливих торгівельних шляхів. Одним із таких є торгівельний шлях, яким сусідня братська держава доставляє свої унікальні обігрівачі до інших країн.

На кордоні Ужляндії та братської держави, де починається цей шлях, розташований спеціальний пропускний пункт, через який щодня проїжджає потяг із величезною кількістю обігрівачів. Зовсім недавно між урядами двох братських країн було погоджено нові правила транзиту обігрівачів через територію Ужляндії на найближчі N днів. Згідно з новим договором має обратися певне число m – максимальна кількість обігрівачів в одному потязі. Тоді з кожного потяга, що транспортує Ai обігрівачів, буде відвантажено рівно Ai-m одиниць іноземної продукції (звичайно, якщо Ai > m, інакше ж потяг рухатиметься без зупинок і нічого відвантажено не буде). Власне це й буде плата за проходження потяга територією Ужляндії, вона еквівалентна грошовим витратам на утримання залізничних колій. Сумарна кількість відвантажених в Ужляндії за N днів обігрівачів повинна бути не менша K, інакше країна зазнає збитків.

Стала відома кількість обігрівачів у потязі в кожен із N днів (ця інформація надається за умовами контракту). Знайдіть максимальне число m, при якому Ужляндія не зазнає економічних збитків.

Формат вхідних даних: В першому рядку записано два числа N, K (1 ≤ N ≤ 106, 1 ≤ K ≤ 2*109). В наступному рядку задано N чисел – кількість обігрівачів у потязі в кожен з N днів, що не перевищує 109.

Формат вихідних даних: В єдиному рядку виведіть одне число – відповідь на задачу, гарантується, що відповідь завжди існує.

Пояснення до прикладу:

Всього територією Ужляндії пройде 4 потяги з 11, 6, 1 та 8 обігрівачами відповідно. Щоби країна не знала збитків, потрібно відвантажити не менше 7 обігрівачів. Очевидно, що максимальне можливе m, яке задовольнить цю умову, буде рівне 6, тоді з потягів буде відвантажено відповідно 5, 0, 0, 2 обігрівачів, що в сумі дорівнює 7 і задовольняє умову.

Лимит времени 1 секунда
Лимит использования памяти 256 MiB
Входные данные #1
4 7
11 6 1 8
Выходные данные #1
6