Підберіть кольори
ліміт часу на тест
1.5 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Міс М любить не тільки придумувати цікаві легенди для задач з програмування, а ще й писати картини, а особливо використовувати гармонійні поєднання кольорів, наприклад, комплементарні кольори з кольорового кола. Але цього разу вона вирішила по-іншому вибирати кольори для своєї картини.

Міс М узяла $$$n$$$ кольорових кіл (можете глянути у примітці, що таке кольорове коло) різних відтінків, які складаються з $$$(a_i+1)$$$ кольору, та вже вибрала один початковий колір на кожному колі, закресливши його як використаний. Потім кожен наступний колір вона буде вибирати за таким алгоритмом:

1. Знаходить найдовший підвідрізок серед усіх кольорових кіл з незакреслених кольорів; якщо таких декілька, то вибирає будь-який.
2. Якщо довжина такого підвідрізку непарна, то бере колір, який рівно посередині, та закреслює його як використаний.
3. Якщо довжина такого підвідрізку парна, то бере один із двох кольорів посередині, та закреслює його як використаний.

Міс М хоче вибрати ще $$$m$$$ кольорів, і їй також цікаво, яка буде максимальна довжина підвідрізку незакреслених кольорів перед тим, як вона вибере $$$(m+n)$$$-й колір.

Вхідні дані

Перший рядок містить два цілі числа $$$n$$$ та $$$m$$$ ($$$1 \leq n \leq 100$$$, $$$1 \leq m \leq 10^{18}$$$) — кількість кольорових кіл та кількість кольорів, які Міс М хоче ще взяти (тобто не враховуючи перші закреслені кольори на кожному колі).

Другий рядок містить $$$n$$$ цілих чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^{18}$$$).

Гарантується, що $$$m$$$ не більше, ніж сума всіх $$$a_i$$$.

Вихідні дані

Виведіть одне ціле число — максимальну довжину підвідрізку незакреслених кольорів перед тим, як Міс М вибере $$$(m+n)$$$-й колір.

Система оцінки

Якщо ваш розв'язок буде правильно працювати для $$$n=1$$$ та $$$a_1 \leq 100$$$, то він отримає принаймні $$$25$$$ балів.

Якщо ваш розв'язок буде правильно працювати для $$$n=1$$$ та $$$a_1 \leq 10^6$$$, то він отримає принаймні $$$50$$$ балів.

Якщо ваш розв'язок буде правильно працювати для $$$n=1$$$, то він отримає принаймні $$$75$$$ балів.

Приклади

Вхідні дані

    1 111

Вихідні дані

    11

Вхідні дані

    1 311

Вихідні дані

    5

Вхідні дані

    1 511

Вихідні дані

    2

Вхідні дані

    1 1091033

Вихідні дані

    15

Вхідні дані

    3 11454034 5912 9134

Вихідні дані

    22

Пояснення

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

Нам дано одне кольорово коло, яке містить $$$12$$$ кольорів. Міс М уже вибрала один колір з кола (на картинці має номер $$$1$$$). Тепер вона хоче вибрати ще $$$3$$$ кольори. Тому послідовність її дій така:

1. Максимальна довжина підвідрізку незакреслених кольорів — $$$11$$$. Тому вибираємо колір, який буде посередині, та помічаємо його номером $$$2$$$.
2. Тепер ми маємо підвідрізок з $$$5$$$ та $$$5$$$ незакреслених кольорів, вибираємо будь-який та посередині підвідрізку вибираємо колір і позначаємо його номером $$$3$$$.
3. Серед підвідрізків $$$2$$$, $$$2$$$ та $$$5$$$ вибираємо $$$5$$$ — це і є максимальна довжина серед підвідрізків незакреслених кольорів перед тим, як Міс М вибере $$$4$$$-й колір.

Кольорове коло з другого прикладу з умови.