Sawing
In this task, you need to cut a sequence of integers.
You are given a sequence of integers that contains an equal number of even and odd numbers. With a limited budget, your goal is to make the maximum number of cuts that divide the sequence into non-empty segments, each containing an equal number of odd and even numbers.
Cuts divide the sequence into consecutive segments. You can think of a cut as a vertical line between two elements. After making the cuts, each element belongs to one segment. For example:
(4, 1, 2, 3, 4, 5, 4, 4, 5, 5) → two cuts → (4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5)
After the cuts, each segment must have an equal number of even and odd numbers. The cost of a cut between numbers x and y is |x - y| bitcoins. Determine the maximum number of cuts you can make while spending no more than B bitcoins.
Input
The first line contains two integers n and B (2 ≤ n ≤ 10000, 2 ≤ B ≤ 10^9) – the size of the sequence and the number of bitcoins you have.
The second line contains n numbers a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 10^9) – the elements of the sequence. The sequence contains an equal number of even and odd elements.
Output
Output a single number – the maximum number of cuts you can make while spending no more than B bitcoins.