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-----

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-----

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


-----Examples-----
Input
6 4
1 2 5 10 15 20

Output
1

Input
4 10
1 3 2 4

Output
0

Input
6 100
1 2 3 4 5 6

Output
2



-----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.

Difficulty: interview

Starter code:

Solutions:


n, B = list(map(int, input().split()))

A = [int(x) for x in input().split()]

odd, even = 0, 0

cuts = []

for i in range(n - 1):
    if A[i] % 2 == 0:
        even += 1
    else:
        odd += 1
    if odd == even:
        cuts += [(abs(A[i] - A[i + 1]), i)]

cuts.sort()

result = 0

for cost, _ in cuts:
    if cost <= B:
        B -= cost
        result += 1


print(result)


n, b = map(int, input().split())
a = list(map(int, input().split()))

ce, co = 0, 0
d = []
for i in range(n - 1):
    if a[i] % 2 == 1: co += 1
    else: ce += 1
    if (ce == co): d.append(abs(a[i] - a[i + 1]))

d.sort()

res = 0
for i in range(len(d)):
    if b >= d[i]:
        res += 1
        b -= d[i]
print(res)

from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque
from collections import Counter


def read():
    return int(input())


def readmap():
    return map(int, input().split())


def readlist():
    return list(map(int, input().split()))


N, B = readmap()
A = readlist()

even = 0
odd = 0
cost = []
for i in range(0, N - 1):
    if A[i] % 2 == 0:
        even += 1
    else:
        odd += 1
    if even == odd:
        cost.append(abs(A[i] - A[i + 1]))

cost.sort()
ans = 0
for c in cost:
    if c > B:
        break
    else:
        ans += 1
        B -= c

print(ans)

#!/usr/bin/env python3

[n, B] = list(map(int, input().strip().split()))
ais = list(map(int, input().strip().split()))

c = [0, 0]
cutcost = []
for i in range(n - 1):
	c[ais[i] % 2] += 1
	if c[0] == c[1]:
		cutcost.append(abs(ais[i] - ais[i + 1]))

cutcost.sort()
cnt = 0
for cost in cutcost:
	if cost <= B:
		cnt += 1
		B -= cost

print (cnt)


n, b = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]

n_odd, n_even = 0, 0
costs = []

for i in range(n - 1):
    if a[i] % 2 == 0:
        n_even += 1
    else:
        n_odd += 1
    if n_even == n_odd:
        costs.append(abs(a[i] - a[i + 1]))

costs.sort()

ans = 0
while ans < len(costs) and costs[ans] <= b:
    b -= costs[ans]
    ans += 1

print(ans)


n, B = (int(x) for x in input().split())
a = [int(x) for x in input().split()]

odd = 0
s = []
for i in range(n - 1):
    if a[i] % 2 == 1:
        odd += 1
    else:
        odd -= 1
    if odd == 0:
        s.append(abs(a[i] - a[i + 1]))

s.sort()
k = 0
i = 0
while i < len(s) and k + s[i] <= B:
    k += s[i]
    i += 1
print(i)

n, m = list(map(int, input().split()))

ls = [int(i) for i in input().split()]

odd_num, even_num = 0, 0

cur_odd = 0
cur_even = 0

ans = []

for i in range(n - 2):
    if ls[i] & 1:
        cur_odd += 1
    else:
        cur_even += 1

    if i >= 1 and cur_odd == cur_even:
        ans.append(abs(ls[i+1] - ls[i]))

ans.sort()

res = 0
for i in ans:
    if m - i >= 0:
        m -= i
        res += 1
    else:
        break

print(res)


n, B = list(map(int, input().split()))
a = list(map(int, input().split()))
# print(n, B, a)

oMe = 0
Bs = []
for i in range(n):
    if a[i] % 2 == 0:
        oMe -= 1
    else:
        oMe += 1
    if oMe == 0 and i + 1 != n:
        Bs.append(abs(a[i] - a[i+1]))
Bs = sorted(Bs)
ans = 0
for i in range(len(Bs)):
    if B - Bs[i] >= 0:
        B -= Bs[i]
        ans += 1
print(ans)


n,m=map(int,input().strip().split())
odd=0
even=0
l=list(map(int,input().strip().split()))
l1=[]
for i in range(n-1):
	if l[i]%2==0:
		even=even+1
	else:
		odd=odd+1
	if odd==even:
		if (l[i]-l[i+1])<0:
			l1.append(l[i+1]-l[i])
		else:
			l1.append(l[i]-l[i+1])
l1.sort()
count=0
sum1=0
for i in l1:
	sum1=sum1+i
	if sum1<=m:
		count=count+1
	else:
		break
print (count)

q,w = list(map(int,input().split()))
a = list(map(int,input().split()))
d = []
k = 0
for i in range(q-1):
    k+=a[i]%2
    if k==i-k+1:
        d.append(abs(a[i]-a[i+1]))
d.sort()
k = 0
i = 0
while (i<len(d))&(k<=w):
    k+=d[i]
    i+=1
if k>w:
    print(i-1)
else:
    print(i)
    


n, b = [int(c) for c in input().split(" ")]
a = [int(c) for c in input().split(" ")]

evenodd = []

evenodd_cur = 0
for i in range(n):
    if a[i] % 2 == 0: evenodd_cur += 1
    else: evenodd_cur -= 1
    evenodd.append(evenodd_cur)

watchlist = []
for i in range(n-1):
    if evenodd[i] == 0:
        watchlist.append((abs(a[i] - a[i+1]), i))

watchlist.sort()
# print(watchlist)

totalcount = 0
for price, index in watchlist:
    if b >= price:
        totalcount += 1
        b -= price
    else:
        break

print(totalcount)

n, b = map(int, input().split())
arr = list(map(int, input().split()))
ne = 0
ch = 0
mass = []
for i in range(n - 1):
    if(arr[i] % 2 == 0):
        ch += 1
    else:
        ne += 1
    if(ch == ne):
        mass.append(abs(arr[i] - arr[i + 1]))
ans = 0
mass.sort()
for i in mass:
    if(i <= b):
        b -= i
        ans += 1
print(ans)

n,k = list(map(int, input().split()))
seq = list(map(int, input().split()))

curr = 0
cut = []

for i in range(n-1):
    if seq[i]%2:
        curr += 1
    else:
        curr -= 1

    if curr == 0:
        cut.append(abs(seq[i]-seq[i+1]))

cut.sort()
ans = 0
currsum = 0

for i in cut:
    currsum += i
    if currsum > k:
        break
    else:
        ans += 1

print(ans)


from math import ceil

t = 1
for test in range(t):
    n,b = list(map(int, input().split()))
    a = list(map(int, input().split()))
    countOdd = 0
    countEven = 0
    cuts = []
    prev = 0
    for i in a:
        if countEven==countOdd:
            cuts.append(abs(prev-i))
        if i%2 == 0:
            countEven+=1
        else:
            countOdd+=1
        prev = i
    cuts[0] = 200 #useless
    cuts.sort()
    ans=0
    cost = 0
    for i in cuts:
        if cost+i>b:
            break
        else:
            ans+=1
            cost+=i
    print(ans)


n, B = list(map(int, input().split()))
a = list(map(int, input().split()))

def solve(a, B):
    diff, k = [], 0
    for i in range(0, len(a)-1):
        if a[i] % 2 == 0: k += 1
        else: k -= 1
        if k == 0:
            diff.append(abs(a[i+1] - a[i]))
    diff.sort()
    s = 0
    for i in range(len(diff)):
        s += diff[i]
        if s > B:return i
    return len(diff)

print(solve(a, B))

#Round 493
#B
from sys import stdin, stdout
from queue import PriorityQueue

def main():
    n, b = [int(i) for i in stdin.readline().split()]
    a = [int(i) for i in stdin.readline().split()]

    q = PriorityQueue()
    evens = 0
    for i in range(n-1):
        if a[i]%2 == 0:
            evens += 1
        else:
            evens -= 1
        if evens == 0:
            q.put(abs(a[i]-a[i+1]))

    count = 0
    while not q.empty():
        smallest = q.get()
        if b >= smallest:
            b -= smallest
            count += 1
        else:
            break

    print(count)
    
main()



def main():
    n, b = list(map(int, input().split()))
    numbers = list(map(int, input().split()))

    values = []
    count = 0
    last_item = 0
    start = False
    for item in numbers:
        if start and count == 0:
            values += [abs(item - last_item)]
        
        if item % 2 == 0:
            count += 1
        else:
            count -= 1
            
        last_item = item
        start = True
    
    answer = 0
    answer_count = 0
    for value in sorted(values):
        if answer + value <= b:
            answer += value
            answer_count += 1
            
    print(answer_count)
    
main()

n,b = [int(x) for x in input().strip().split(' ')]
a=[int(x) for x in input().strip().split(' ')]
odd=0
eve=0
c=[]
for i in range(n):
    if a[i]&1:
        odd+=1
    else:
        eve+=1
    if i<(n-1) and odd==eve:
        c.append(abs(a[i+1]-a[i]))
c.sort()
l = len(c)
j=0
ans=0
while j<l:
    b-=c[j]
    if b>=0:
        ans+=1
    else:
        break
    j+=1
print(ans)

n,c=[int(x) for x in input().split()]
ns=[int(x)for x in input().split()]
odd=0
cost=[]
for i in range(n):
    if (ns[i]&1)==1:
        odd+=1
    else:
        odd-=1
    if odd==0:
        if i<n-1:
            cost.append(abs(ns[i+1]-ns[i]))
# print(cost)
cost.sort()
sum=0
p=False
for i in range(len(cost)):
    sum+=cost[i]
    if sum>c:
        print(i)
        p=True
        break
if not p:
    print(len(cost))

n, b = input().split()
n = int(n)
b = int(b)
a = [int(x) for x in input().split()]
odd = 0
not_odd = 0
pos = list()
for i in range(n-1):
    if a[i] % 2 == 0:
        not_odd += 1
    else:
        odd += 1
    if not_odd == odd:
          pos.append(abs(a[i+1] - a[i]))
pos.sort()
sum = 0
count = 0
for i in range(len(pos)):
    if sum + pos[i] <= b:
        sum += pos[i]
        count += 1
print(count)


n,b = list(map(int,input().split()))
ai = list(map(int,input().split()))
ai2 = [0] * n
temp1 = 0
for i in range(n-1):
    if ai[i] % 2 == 0:
        temp1 += 2
    if temp1 == i + 1:
        ai2[i] = 1
        
ai4 = []

temp1 = 0
for i in range(n-1,0,-1):
    if ai[i] % 2 == 0:
        temp1 += 2
    if temp1 == n - i:
        if ai2[i-1] == 1:
            ai4 += [abs(ai[i] - ai[i-1])]
ai4.sort()
ans = 0
i = 0
while  i < len(ai4) and b >= ai4[i]:
    b -= ai4[i]
    ans += 1
    i += 1
print(ans)


n, b = list(map(int, input().split()))
a = list(map(int, input().split()))
e = [0] * len(a)
o = [0] * len(a)

for i, elem in enumerate(a):
    e[i] = e[i - 1]
    o[i] = o[i - 1]

    if elem % 2 == 0:
        e[i] += 1
    else:
        o[i] += 1

cuts = 0
price = 0

while True:
    min_i = -1
    min_val = 1e9
    for i in range(len(a) - 1):
        if e[i] == o[i]:
            if abs(a[i] - a[i + 1]) < min_val:
                min_val = abs(a[i] - a[i + 1])
                min_i = i
    if min_i != -1 and price + min_val <= b:
        cuts += 1
        price += min_val
        a[min_i] = 1e9
    else:
        break

print(cuts)