Розпил#8781
Існує багато речей, які можна розрізати — дерева, гантелі (ті, що золоті), бюджетні кошти. У цій задачі потрібно розділити послідовність цілих чисел.
Вам задано послідовність цілих чисел, яка містить однакову кількість парних і непарних чисел. За умов обмеженого бюджету необхідно зробити якомога більше розрізів, які поділять послідовність на непусті відрізки, у кожному з яких кількість парних і непарних чисел однакова.
Розрізи ділять послідовність на неперервні відрізки, що йдуть один за одним. Можна уявити розріз як вертикальне відділення між парою елементів. Після розрізів кожен елемент належить до певного відрізку. Наприклад, можливий варіант:
(4, 1, 2, 3, 4, 5, 4, 4, 5, 5) → два розрізи → (4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5)Після розрізів на кожному з відрізків кількість парних і непарних чисел повинна бути однаковою.Вартість розрізу між числами і дорівнює |x - y| біткоїнів. Знайдіть максимальну кількість розрізів, які можна зробити, витративши не більше біткоїнів.
Перший рядок містить два цілі числа і (2 \leq n \leq 10000, 2 \leq B \leq 10^9) — розмір послідовності і кількість біткоїнів, які у вас є.
Другий рядок містить чисел a_1, a_2, \ldots, a_n (0 \leq a_i \leq 10^9) — елементи послідовності. Послідовність містить однакову кількість парних і непарних чисел.
Виведіть одне число — максимальну кількість розрізів, які можна зробити, витративши не більше біткоїнів.
Приклад 1
Приклад 2
Приклад 3