记录编号	596202	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO24 Open Gold]Cowreography	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	2.196 s
提交时间	2024-10-23 15:05:32	内存使用	7.17 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 1e6+10;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n,k,m;
char c;
int a[N],b[N];
ll ans = 0;
set<pii>s[2];
int main(){
	freopen("cowreography.in","r",stdin);
	freopen("cowreography.out","w",stdout);
	n = read(),k = read();
	for(int i = 1;i <= n;i++){
		cin>>c;
		if(c == '1')a[i] = 1;
	}
	for(int i = 1;i <= n;i++){
		cin>>c;
		if(c == '1')b[i] = 1;
	}
	for(int i = 1;i <= n;i++){
		if(a[i] == b[i])continue;
		if(s[b[i]].size()){
			auto x = s[b[i]].lower_bound(make_pair(i % k,0));
			if(x == s[b[i]].end())x = s[b[i]].begin();
			ans += (i - (*x).se+ k - 1) / k;
			s[b[i]].erase(x);
		}
		else s[a[i]].insert({i % k,i});
	}
	printf("%lld\n",ans);
	

	return 0;

}