B. Cuttingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere 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.InputFirst 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 numbersOutputPrint the maximum possible number of cuts which can be made while spending no more than B bitcoins.ExamplesInput6 41 2 5 10 15 20Output1Input4 101 3 2 4Output0Input6 1001 2 3 4 5 6Output2NoteIn 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.
Input6 41 2 5 10 15 20
Output1
['dp', 'greedy', 'sortings', '*1200']