Країна Ужляндія має вигідне географічне розташування – її територія знаходиться на перетині важливих торговельних шляхів. Одним із таких є торговельний шлях, яким сусідня братська держава доставляє свої унікальні обігрівачі до інших країн.
На кордоні Ужляндії та братської держави, де починається цей шлях, розташований спеціальний пропускний пункт, через який щодня проїжджає потяг із величезною кількістю обігрівачів. Зовсім недавно між урядами двох братських країн було погоджено нові правила транзиту обігрівачів через територію Ужляндії на найближчі днів. Згідно з новим договором має обратися певне число – максимальна кількість обігрівачів в одному потязі. Тоді з кожного потяга, що транспортує A_i обігрівачів, буде відвантажено рівно A_i - m одиниць іноземної продукції (звичайно, якщо A_i > m, інакше ж потяг рухатиметься без зупинок і нічого відвантажено не буде). Власне це й буде плата за проходження потяга територією Ужляндії, вона еквівалентна грошовим витратам на утримання залізничних колій. Сумарна кількість відвантажених в Ужляндії за днів обігрівачів повинна бути не менша , інакше країна зазнає збитків.
Стала відома кількість обігрівачів у потязі в кожен із днів (ця інформація надається за умовами контракту). Знайдіть максимальне число , при якому Ужляндія не зазнає економічних збитків.
В першому рядку записано два числа , (1 \le N \le 10^6, 1 \le K \le 2 \cdot 10^9). В наступному рядку задано чисел – кількість обігрівачів у потязі в кожен з днів, що не перевищує 10^9.
В єдиному рядку виведіть одне число – відповідь на задачу, гарантується, що відповідь завжди існує.
Приклад 1
Всього територією Ужляндії пройде 4 потяги з 11, 6, 1 та 8 обігрівачами відповідно. Щоби країна не знала збитків, потрібно відвантажити не менше 7 обігрівачів. Очевидно, що максимальне можливе , яке задовольнить цю умову, буде рівне 6, тоді з потягів буде відвантажено відповідно 5, 0, 0, 2 обігрівачів, що в сумі дорівнює 7 і задовольняє умову.
N \le 300 – не менше 20 балів
N \le 10000 – не менше 40 балів