eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Розпил

Розпил

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Існує достатньо багато речей, які можна розпилити – дерева, гантелі (ті що золоті), бюджетні кошти. В цій задачі необхідно розпилити послідовність цілих чисел.

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

Розрізи розділяють послідовність на неперервні відрізки, які ідуть один за іншим. Ви можете уявляти собі розріз як вертикальне розділення між парою елементів. Таким чином, після розрізів кожний елемент належить до одного відрізку. Наприклад, можливий випадок:

(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 біткоїнів.

Пример

Входные данные #1
6 4
1 2 5 10 15 20
Выходные данные #1
1
Входные данные #2
4 10
1 3 2 4
Выходные данные #2
0
Входные данные #3
6 100
1 2 3 4 5 6
Выходные данные #3
2