easy cut problem

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在序列中将a[i]和a[i+1]切割开的花费为abs ( a[i] - a[i+1] ) ,现在要使切割后的每一段中的奇数和偶数数量相等,问总花费不超过m的最大切割次数,保证序列中的奇数与偶数数量相等。

Input

n,m。代表序列长度与最大花费。

第二行n个正整数表示序列。

1 < n , m <=100

Output

一个整数代表最大切割次数。

Sample Input

6 100
1 2 3 4 5 6

Sample Output

2

Hint

对于样例,应该在2和3中间,4和5中间分别切割一次,切割后变成12,34,56,对于第一块中的数字,奇数个数和偶数个数都为1,此符合题目要求,第二块第三块同理。

2和3中间的切割花费为abs(2-3),

4和5中间的切割花费为abs(4-5),

花费总额为2小于最大总花费。

Source

行走的二叉树