Поїдання булочок#9062
Кратос і Атрей вирішили поїсти булочок. Щоб урізноманітнити процес, Кратос приготував булочок і запропонував влаштувати змагання з швидкісного поїдання.
І Кратос, і Атрей будуть їсти по булочок. Все закінчилося так само швидко, як і почалося. Фрейя таємно спостерігала за цим змаганням і помітила кілька особливостей:
Обидва учасники змагання з'їли рівно по булочок.
За одну дію Кратос або Атрей з'їдали або одну, або дві булочки.
Кожного разу, коли хтось із них робив дію, він записував скільки булочок з'їдав.
Після того, як Кратос з Атреєм пішли, Фрейя знайшла їх "протокол". На жаль, для кожної дії записано, скільки булочок було з'їдено, але не записано, хто саме їх їв.
Фрейя пам'ятає, що Кратос у деякий момент змагання виглядав беззаперечним лідером, оскільки з'їв булочок значно більше ніж Атрей. Вона просить вас за даним протоколом визначити, який найбільший відрив міг бути у Кратоса протягом змагання.
У першому рядку задано два цілих числа і k~(2 \le n \le 10^5, 1 \le k \le n) — число записів у протоколі та число булочок, з'їдених кожним з учасників.
У другому рядку задано чисел a_i~(1 \le a_i \le 2) — дані протоколу. Гарантовано, що протокол коректний: можна розділити a_i на дві множини так, щоб сума чисел в обох множинах була рівна .
Виведіть одне ціле число — найбільший відрив Кратоса протягом змагання.
Приклад 1