Підберіть кольори

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

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

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

2. Якщо довжина такого підвідрізку непарна, то бере колір, який рівно посередині, та закреслює його як використаний.

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

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

Вхідні дані

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

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

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

Вихідні дані

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

Приклади

Примітка

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

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

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

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

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

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

Оцінювання

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

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

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