Cutting

## 题目描述 有一个整数序列，其偶数和奇数的数量相同。给定有限的预算，您需要尽可能多地进行切割，使每个结果段具有相同数量的奇数和偶数。 “切割”操作将一个序列分成 $2$ 个连续的段。您可以将每次“切割”看作是序列中两个相邻元素之间的中断。所以在切割之后每个元素恰好属于一个片段。 举个例子，$[4,1,2,3,4,5,4,4,5,5]\to$ 两次“切割”操作 $\to[4,1|2,3,4,5|4,4,5,5]$。在每个切割后的段上，偶数元素的个数应该等于奇数元素的个数。 在元素 $x$ 和元素 $y$ 之间进行一次“切割”操作的价值为 $|x-y|$ 元。请问，在 $B$ 元内，最多可以切割几次？ ## 输入格式 第一行，输入 $2$ 个整数，$n$ 和 $B$（$2\le n\le 100$，$1\le B\le 100$），分别代表元素个数和你目前有的预算。 接下来的一行，输入 $n$ 个整数，$a_1,a_2,\cdots,a_n$，表示整个段内的元素。其中包含相同个数的奇数和偶数。 ## 输出格式 输出最多的“切割”次数，使其可以作出，且支出不超过 $B$ 元。

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.

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

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

6 4
1 2 5 10 15 20

1

4 10
1 3 2 4

0

6 100
1 2 3 4 5 6

2

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.