e-olymp
Змагання

2018 School second team season olympiad, Basic nomination

Поедание крыс

Кратос и Атрей решили поесть жареных крыс. Чтобы разнообразить процесс, Кратос приготовил 2k крыс и предложил устроить соревнование по скоростному поеданию.

И Кратос и Атрей будут есть по k жареных крыс. Все закончилось также быстро, как и началось. Фрейя тайно наблюдала за этим состязанием и заметила несколько особенностей:

  • Оба участника состязания съели ровно по k крыс.
  • За одно действие Кратос либо Атрей съедали либо одну, либо две крысы.
  • Каждый раз, когда кто-то из них делал действие, он записывал сколько крыс съедал.

После того, как Кратос с Атреем ушли, Фрейя нашла их "протокол". К сожалению, для каждого действия записано, сколько крыс было съедено, но не записано, кто именно их ел.

Фрейя помнит, что Кратос в некоторый момент состязания выглядел безоговорочным лидером, так как съел крыс сильно больше чем Атрей. Она просит вас по данному протоколу, определить, какой наибольший отрыв мог быть у Кратоса на протяжении состязания.

Входные данные

В первой строке заданы два целых числа n и k (2n105, 1kn) - число записей в протоколе и число крыс, съеденных каждым из участников.

Во второй строке заданы n чисел ai (1ai2) - данные протокола. Гарантируется, что протокол корректен: можно разделить ai на два множества так, чтобы сумма чисел в обоих множествах была равна k.

Выходные данные

Выведите одно целое число - наибольший отрыв Кратоса на протяжении состязания.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 2
1 2 1
Вихідні дані #1
1
Джерело 2018 Цикл Интернет-олимпиад для школьников, вторая командная олимпиада сезона, базовая номинация, 20 октября, Задача А