有很多东西可以砍伐——树木、纸张、“绳子”。在这个问题中,您将切割一个整数序列。
有一个整数序列,其中包含相同数量的偶数和奇数。在预算有限的情况下,您需要进行尽可能多的切割,以便每个结果段都具有相同数量的奇数和偶数整数。
将序列剪切为连续(连续)的片段。您可以将每次剪切视为序列中两个相邻元素之间的中断。因此,切割后每个元素都属于一个片段。比如说,$$$[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$$$ 比特币的情况下可以进行的最大可能削减次数。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) 和一个整数 $$$B$$$ ($$$1 \le B \le 100$$$) - 序列中的元素数量和您拥有的比特币数量。
第二行包含 $$$n$$$ 整数:$$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 100$$$) — 序列的元素,其中包含相同数量的偶数和奇数
输出
打印花费不超过 $$$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
注意
在第一个示例中,最佳答案是在 $$$2$$$ 和 $$$5$$$ 之间分割序列。此次削减的价格相当于 $$$3$$$ 比特币。
在第二个样本中,即使有无限数量的比特币,也不可能进行一次切割。
在第三个示例中,序列应在 $$$2$$$ 和 $$$3$$$ 之间以及 $$$4$$$ 和 $$$5$$$ 之间剪切。削减的总价格为 $$$1 + 1 = 2$$$ 比特币。