Nhân dịp Black Friday, lastPledge quyết định mua một món quà để tặng crush. Món quà là một dãy số ~a~ gồm ~n~ phần tử, tuy nhiên, vì đây là hàng sale off nên chất lượng không được tốt lắm. Vì vậy, lastPledge muốn tự tay chỉnh sửa lại món quà.

lastPledge sẽ thực hiện thao tác sau vô số lần. Ở lần thứ ~i~, anh ấy sẽ tăng giá trị của ~a_{p_i}~ thêm ~x_i~. Tuy nhiên, vì một số lý do kĩ thuật, ~x_i \ge x_{i - 1}~ với mọi ~i > 0~.

Một dãy số được gọi là dễ thương nếu bất kì dãy con liên tiếp độ dài ~k~ nào của nó đều có tổng chia hết cho ~2~. Vì không muốn thay đổi món quà ban đầu quá nhiều, lastPledge muốn thực hiện ít thao tác nhất có thể để dãy số ban đầu trở nên dễ thương.

Hãy giúp lastPledge chuẩn bị món quà dễ thương nhất để tặng cho crush nhé!

Input

Dòng đầu tiên gồm ~2~ số nguyên dương ~n~ - độ dài dãy ~a~ và ~k~ ~(k \leq n \leq 10^6)~.

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ thể hiện các phần tử của dãy ~a~ (~0 \le a_i \le 10^9~).

Output

Một dòng duy nhất chứa đáp án của bài toán: số lượng thao tác ít nhất để làm dãy ~a~ trở nên dễ thương.

Sample Input 1

5 3
1 10 1 2 9

Sample Output 1

2

Notes

Ở test ví dụ trên, ta có thể làm dãy ~a = [1, 10, 1, 2, 9]~ trở nên dễ thương trong ~2~ thao tác:

• Ở lượt thứ 1: ta chọn ~p_1 = 4~ và ~x_1 = 3~. Lúc này, ~a = [1, 10, 1, 5, 9]~.
• Ở lượt thứ 2: ta chọn ~p_2 = 5~ và ~x_2 = 7~. Lúc này, ~a = [1, 10, 1, 5, 16]~.

Sau ~2~ thao tác, tất cả các dãy con liên tiếp độ dài ~3~ đều có tổng chia hết cho ~2~.