题目名称

宝石排列

题目描述

小码的爷爷是著名魔法宝石收藏家，他有一串魔法宝石，每颗宝石非红（1）即蓝（0）。红色宝石魔力强大，但两颗相邻红宝石靠太近魔力会互相干扰致宝石失效。

爷爷告诉小码规则：任何两颗相邻红宝石之间的距离必须是魔法数字 $m$ 的倍数，“距离”指在宝石串中的位置差。例如 $m = 2$ 时，相邻红宝石位置差须为2、4等。

小码需通过翻转宝石颜色（红变蓝或蓝变红）调整宝石串满足规则，每次翻转耗一点魔力，小码想用最少翻转次数完成任务，求最少翻转次数。

输入格式

• 第一行：两个整数 $n$（宝石数量）和 $m$（魔法数字） 。
• 第二行：$n$ 个数字（0或1），表示宝石初始颜色（0 = 蓝色，1 = 红色） 。

输出格式

一个整数，表示最少需要翻转多少次宝石颜色才能满足规则。

输入输出样例 #1

输入 #1

6 3
1 0 0 1 0 1

输出 #1

1

样例1解释

初始宝石排列为红、蓝、蓝、红、蓝、红。第1个和第4个宝石距离是3（符合），但第4个和第6个距离是2（不符合3的倍数）。把第6个宝石翻转，此时红色宝石只有第1个和第4个，距离是3，符合要求。

输入输出样例 #2

输入 #2

7 2
1 0 1 0 1 0 1

输出 #2

0

样例2解释

初始宝石排列为红、蓝、红、蓝、红、蓝、红。检查相邻宝石距离：第1和第3距离2（符合）；第3和第5距离2（符合）；第5和第7距离2（符合）。已满足要求，无需翻转。

数据范围

• 10%的数据满足：$1 \leq n \leq 10^5$，$m = 1$
• 20%的数据满足：$1 \leq n \leq 10^5$，$m = 2$
• 20%的数据满足：$1 \leq m \leq n \leq 10^3$
• 50%的数据满足：$1 \leq m \leq n \leq 10^5$