Tèo thích cắt rất nhiều thứ - cây cối, giấy, "dây thừng". Trong bài toán này, Tèo sẽ nhờ bạn cắt một dãy số nguyên.

Có một dãy số nguyên chứa số lượng số chẵn và số lượng số lẻ bằng nhau. Với ngân sách hạn chế, bạn cần thực hiện số lần cắt tối đa có thể sao cho mỗi đoạn kết quả sẽ có cùng số lượng số nguyên chẵn và lẻ.

Mỗi lần cắt là một khoảng ngắt giữa hai phần tử liền kề trong một mảng. Vậy sau khi cắt mỗi phần tử thuộc đúng một đoạn. Ví dụ : ~ [ 6 , 3 , 4 , 5 , 6 , 7 , 6 , 6 , 7 , 7 ] \to ~ ba lần cắt ~ \to [ 6, 3 | 4 , 5 | 6 , 7 | 6 , 6 , 7 , 7 ]~ . Trên mỗi đoạn số phần tử chẵn bằng số phần tử lẻ.

Chi phí cắt giảm giữa hai phần tử ~x~ và ~y~ là ~|x−y|~ đồng. Tìm số lần cắt giảm tối đa có thể được thực hiện trong khi chi tiêu không quá ~B~ đồng.

Dữ liệu vào

• Dòng đầu tiên của đầu vào chứa một số nguyên ~N~ (~2 \leq N \leq 10^5~) và một số nguyên ~B~ (~1 \leq B \leq 10^9~) — số phần tử trong chuỗi và số tiền bạn có.

• Dòng thứ hai chứa ~N~ số nguyên: ~a_1, a_2, ..., a_N (1 \leq a_i \leq 10^6) ~ — các phần tử của dãy chứa số chẵn và số lẻ bằng nhau.

Kết quả ra

• In số lần cắt tối đa có thể được thực hiện trong khi chi tiêu không quá ~B~ đồng.

Ràng buộc

• Subtask ~1~ (~20 \%~) : ~2 \leq N \leq 20~.
• Subtask ~2~ (~30 \%~) : ~2 \leq N \leq 1000~, ~ 1 \leq a_{i}, B \leq 5000~.
• Subtask ~3~ (~50 \%~) : Không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vào

10 4
6 1 6 5 6 7 6 6 7 7

Kết quả ra

2

Giải thích

Ta có thể cắt dãy số như sau: ~[ 6, 1 , 6 , 5 | 6 , 7 | 6 , 6 , 7 , 7 ]~.

• Chi phí lần cắt thứ nhất : ~ |5 - 6| = 1 ~.
• Chi phí lần cắt thứ hai : ~ |7 - 6| = 1 ~.
• Tổng chi phí hai lần cắt là ~2~.