Розпил
Існує достатньо багато речей, які можна розпилити – дерева, гантелі (ті що золоті), бюджетні кошти. В цій задачі необхідно розпилити послідовність цілих чисел.
Вам задана послідовність цілих чисел, яка містить однакову кількість парних і непарних чисел. В умовах обмеженого бюджету, потрібно зробити максимальну кількість розрізів, які поділять послідовність на непусті відрізки, на кожному з яких кількість непарних і парних чисел однакова.
Розрізи розділяють послідовність на неперервні відрізки, які ідуть один за іншим. Ви можете уявляти собі розріз як вертикальне розділення між парою елементів. Таким чином, після розрізів кожний елемент належить до одного відрізку. Наприклад, можливий випадок:
(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 біткоїнів.