Cutting
Contest: Codeforces Round 493 (Div. 2)
Difficulty rating: 1200
Tags: dp, greedy, sortings

There are a lot of things which could be cut — trees, paper, "the rope". In this problem you are going to cut a sequence of integers.

There is a sequence of integers, which contains the equal number of even and odd numbers. Given a limited budget, you need to make maximum possible number of cuts such that each resulting segment will have the same number of odd and even integers.

Cuts separate a sequence to continuous (contiguous) segments. You may think about each cut as a break between two adjacent elements in a sequence. So after cutting each element belongs to exactly one segment. Say, $$$[4, 1, 2, 3, 4, 5, 4, 4, 5, 5]$$$ $$$\to$$$ two cuts $$$\to$$$ $$$[4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5]$$$. On each segment the number of even elements should be equal to the number of odd elements.

The cost of the cut between $$$x$$$ and $$$y$$$ numbers is $$$|x - y|$$$ bitcoins. Find the maximum possible number of cuts that can be made while spending no more than $$$B$$$ bitcoins.

Input format:
First line of the input contains an integer $$$n$$$ ($$$2 \le n \le 100$$$) and an integer $$$B$$$ ($$$1 \le B \le 100$$$) — the number of elements in the sequence and the number of bitcoins you have.

Second line contains $$$n$$$ integers: $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 100$$$) — elements of the sequence, which contains the equal number of even and odd numbers

Output format:
Print the maximum possible number of cuts which can be made while spending no more than $$$B$$$ bitcoins.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample the optimal answer is to split sequence between $$$2$$$ and $$$5$$$. Price of this cut is equal to $$$3$$$ bitcoins.

In the second sample it is not possible to make even one cut even with unlimited number of bitcoins.

In the third sample the sequence should be cut between $$$2$$$ and $$$3$$$, and between $$$4$$$ and $$$5$$$. The total price of the cuts is $$$1 + 1 = 2$$$ bitcoins.

Example input:
6 4
1 2 5 10 15 20

Example output:
1

Example input:
4 10
1 3 2 4

Example output:
0

Editorial:
It is possible to proof, that cut after $$$i$$$-th number can be done if and only if the prefix of length $$$i$$$ contains equal number of odd and even numbers.
This way each cut can be done or not done independently of all other cuts (except the budget issue).
Why it is true?
Let's proof that criterion is sufficient. If you make some set of cuts, where each cut is valid according to criterion above, than the result would be correct — each part of result lies between to cuts, and if prefixes which correspond to cuts have same number of odds-evens, than the part between also will have these numbers equal.
Let's show that the condition is required — if there is some set of cuts, which produces correct parts, than each part has same number of odds-evens, and than all prefixes, which correspond to cuts also have the same number of odds-evens.
This way each cut can be done independently, so you can identify all valid cuts, order them by cut-price, and take greedy from the beginning of the list while the budget allows.