B. Распил
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Существует достаточно много вещей, которые можно распилить — деревья, гантели (которые золотые), бюджетные средства. В этой задаче вам предстоит распилить последовательность целых чисел.

Вам дана последовательность целых чисел, содержащая одинаковое количество чётных и нечётных чисел. Требуется в условиях ограниченного бюджета провести максимальное число разрезов, которые разделят на последовательность на непустые отрезки, на каждом из которых количество чётных чисел равно количеству нечётных чисел.

Разрезы разделяют последовательность на непрерывные подряд идущие отрезки. Вы можете думать о разрезе, как о вертикальном разделителе между парой соседних элементов. Таким образом, после разрезов каждый элемент принадлежит ровно одному отрезку. Например, возможен случай: $$$[4, 1, 2, 3, 4, 5, 4, 4, 5, 5]$$$ $$$\to$$$ два разреза $$$\to$$$ $$$[4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5]$$$. После разрезов на каждом отрезке количество четных элементов должно быть равно количеству нечётных.

Стоимость разреза между числами $$$x$$$ и $$$y$$$ составляет $$$|x - y|$$$ биткоинов. Найдите максимальное количество разрезов, которые можно сделать, потратив при этом не более $$$B$$$ биткоинов.

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

Первая строка содержит целое число $$$n$$$ ($$$2 \le n \le 100$$$) и целое число $$$B$$$ ($$$1 \le B \le 100$$$) — размер последовательности и количество биткоинов, которое у вас есть.

Вторая строка содержит $$$n$$$ чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 100$$$) — элементы последовательности. Последовательность содержит одинаковое количество чётных и нечётных элементов.

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

Выведите одно число — максимальное количество разрезов, которые можно провести, потратив не более $$$B$$$ биткоинов.

Примеры
Входные данные
6 4
1 2 5 10 15 20
Выходные данные
1
Входные данные
4 10
1 3 2 4
Выходные данные
0
Входные данные
6 100
1 2 3 4 5 6
Выходные данные
2
Примечание

В первом примере следует разрезать между числом $$$2$$$ и $$$5$$$, стоимость разреза составит $$$3$$$ биткоина.

Во втором примере нельзя сделать ни одного разреза вне зависимости от числа биткоинов.

В третьем примере последовательность следует разрезать между числами $$$2$$$ и $$$3$$$ и между числами $$$4$$$ и $$$5$$$. Суммарная стоимость составляет $$$1 + 1 = 2$$$ биткоина.