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

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

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

Міс М хоче вибрати ще ~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~ балів.

Пояснення

До другого прикладу:

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

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

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

Приклад вхідних даних

1 1
11

Приклад вихідних даних

11

Приклад вхідних даних

1 3
11

Приклад вихідних даних

5

Приклад вхідних даних

1 5
11

Приклад вихідних даних

2

Приклад вхідних даних

1 109
1033

Приклад вихідних даних

15

Приклад вхідних даних

3 1145
4034 5912 9134

Приклад вихідних даних

22