Распил
В этой задаче вам предстоит распилить последовательность целых чисел.
Дана последовательность целых чисел, в которой количество четных и нечетных чисел одинаково. В условиях ограниченного бюджета необходимо сделать максимальное количество разрезов, разделяющих последовательность на непустые отрезки, в каждом из которых количество четных и нечетных чисел одинаково.
Разрезы делят последовательность на последовательные отрезки. Представьте разрез как вертикальную линию между двумя элементами. После разрезов каждый элемент принадлежит одному из отрезков. Например:
(4, 1, 2, 3, 4, 5, 4, 4, 5, 5) → два разреза → (4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5)
На каждом отрезке после разрезов количество четных и нечетных чисел должно быть одинаковым. Стоимость разреза между числами x и y равна |x - y| биткоинов. Найдите максимальное количество разрезов, которые можно сделать, потратив не более B биткоинов.
Входные данные
Первая строка содержит два целых числа n и B (2 ≤ n ≤ 10000, 2 ≤ B ≤ 10^9) – размер последовательности и количество биткоинов, которые у вас есть.
Вторая строка содержит n чисел a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 10^9) – элементы последовательности. Последовательность содержит одинаковое количество четных и нечетных элементов.
Выходные данные
Выведите одно число – максимальное количество разрезов, которые можно сделать, потратив не более B биткоинов.