자르기

자를 수 있는 것은 나무, 종이, "the rope" 등 아주 많다. 이 문제에서는 정수 수열을 자른다.

짝수와 홀수의 개수가 같은 정수 수열이 있다. 제한된 예산으로, 잘라서 생긴 각 구간에 홀수와 짝수가 같은 개수만큼 포함되도록 하면서 가능한 한 많은 횟수로 잘라야 한다.

자르면 수열이 연속된 구간들로 나뉜다. 각 자르기는 수열에서 인접한 두 원소 사이를 끊는 것이라고 생각할 수 있다. 따라서 자른 뒤 각 원소는 정확히 하나의 구간에 속한다. 예를 들어, $[4, 1, 2, 3, 4, 5, 4, 4, 5, 5]$ → 두 번 자르기 → [4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5]이다. 각 구간에서 짝수 원소의 개수는 홀수 원소의 개수와 같아야 한다.

x번째 수와 y번째 수 사이를 자르는 비용은 |x - y| 비트코인이다. 최대 B 비트코인을 사용하여 자를 수 있는 최대 횟수를 구한다.

입력의 첫 번째 줄에는 정수 n (2 ≤ n ≤ 100)와 정수 B (1 ≤ B ≤ 100)가 주어진다. 이는 각각 수열의 원소 개수와 보유한 비트코인의 개수이다.

두 번째 줄에는 n개의 정수 $a_1$, $a_2$, ..., $a_n$ (1 ≤ $a_i$ ≤ 100)가 주어진다. 이들은 수열의 원소이며, 수열에는 짝수와 홀수가 같은 개수만큼 포함되어 있다.

최대 B 비트코인을 사용하여 자를 수 있는 최대 횟수를 출력한다.

첫 번째 예제에서 최적의 답은 수열을 2와 5 사이에서 나누는 것이다. 이 자르기의 비용은 3 비트코인이다.

두 번째 예제에서는 비트코인이 무제한으로 있더라도 단 한 번도 자를 수 없다.

세 번째 예제에서는 수열을 2와 3 사이, 그리고 4와 5 사이에서 잘라야 한다. 자르기의 총비용은 1 + 1 = 2 비트코인이다.