rt,赛时没调出来。

# include <bits/stdc++.h>
# define int long long
# define pb push_back
using namespace std;
const int N = 5e5 + 5;
int c,n,m;
char a[5][N];
int v[5][N],dp[5][N],v2[5][N][2],f[5][1005][1005];
void solve () {
	int ans = 0,flag = 1;
	cin >> n >> m;
	for (int i = 1;i <= n;++i) cin >> a[1][i];
	for (int i = 1;i <= n;++i) cin >> a[2][i] , flag &= (a[1][i] == a[2][i]);
	if (flag || n >= 1000) {
		for (int i = 1;i <= n;++i) {
			if (a[1][i] == '1' && a[2][i] == '1') v[0][i] = 1 , v[1][i] = 1 , v[2][i] = 2;
			else if (a[1][i] == '1' && a[2][i] == '0') v[0][i] = -1,v[1][i] = -1,v[2][i] = 0;
			else if (a[1][i] == '0' && a[2][i] == '1') v[0][i] = -1,v[1][i] = -1,v[2][i] = 0;
			else if (a[1][i] == '0' && a[2][i] == '0') v[0][i] = -1,v[1][i] = -1,v[2][i] = -2; 
		}
		for (int i = 1;i <= n;++i) {
			dp[0][i] = max(max(dp[0][i - 1],dp[2][i - 1]) + v[0][i],v[0][i]);
			dp[1][i] = max(max(dp[1][i - 1],dp[2][i - 1]) + v[1][i],v[1][i]);
			dp[2][i] = max(max(dp[0][i - 1],max(dp[1][i - 1],dp[2][i - 1])) + v[2][i],v[2][i]);
			ans = max(ans,max(dp[0][i],max(dp[1][i],dp[2][i])));
		}
		cout << ans << "\n";
	}
	else {
		ans = -1e18;
		for (int i = 1;i <= n;++i) {
			if (a[1][i] == '1' && a[2][i] == '1') v2[0][i][0] = v2[0][i][1] = 1 , v2[1][i][0] = v2[1][i][1] = 1 , v2[2][i][0] = v2[2][i][1] =  2;
			else if (a[1][i] == '1' && a[2][i] == '0') v2[0][i][0] = 1,v2[0][i][1] = -1,v2[1][i][0] = 1,v2[1][i][1] = -1,v2[2][i][0] = v2[2][i][1] = 0;
			else if (a[1][i] == '0' && a[2][i] == '1') v2[0][i][0] = -1,v2[0][i][1] = 1,v2[1][i][0] = 1,v2[1][i][1] = -1,v2[2][i][0] = v2[2][i][1] = 0;
			else if (a[1][i] == '0' && a[2][i] == '0') v2[0][i][0] = -1,v2[0][i][1] = -1,v2[1][i][0] = -1,v2[1][i][1] = -1,v2[2][i][0] = v2[2][i][1] = -2;
		}
		memset (f,0x7f,sizeof f);
		for (int i = 1;i <= n;++i) {
			/*单独做一遍*/
			f[0][i][0] = min(min(f[0][i - 1][0],f[2][i - 1][0]) + v2[0][i][0],v2[0][i][0]);
			f[1][i][0] = min(min(f[1][i - 1][0],f[2][i - 1][0]) + v2[1][i][0],v2[1][i][0]);
			f[2][i][0] = min(min(f[0][i - 1][0],min(f[1][i - 1][0],f[2][i - 1][0])) + v2[2][i][0],v2[2][i][0]);
			ans = max(ans,max(max(f[0][i][0],f[1][i][0]),f[2][i][0]));
		} 
		for (int i = 1;i <= n;++i) {
			for (int j = 1;j <= min(i,m);++j) {
				f[0][i][j] = min(min(min(f[0][i - 1][j] + v2[0][i][0],f[2][i - 1][j] + v2[0][i][0]),min(f[0][i - 1][j - 1] + v2[0][i][1],f[2][i - 1][j - 1] + v2[0][i][1])),v2[0][i][min(j,1ll)]);
				f[1][i][j] = min(min(min(f[1][i - 1][j] + v2[1][i][0],f[2][i - 1][j] + v2[1][i][0]),min(f[1][i - 1][j - 1] + v2[1][i][1],f[2][i - 1][j - 1] + v2[1][i][1])),v2[1][i][min(j,1ll)]);
				f[2][i][j] = min(min(min(f[1][i - 1][j] + v2[2][i][0],min(f[2][i - 1][j] + v2[2][i][0],f[0][i - 1][j] + v2[2][i][0])),min(f[1][i - 1][j - 1] + v2[2][i][1],min(f[2][i - 1][j - 1] + v2[2][i][1],f[0][i - 1][j - 1] + v2[2][i][1]))),v2[2][i][min(j,1ll)]);
				ans = max(ans,max(max(f[0][i][j],f[1][i][j]),f[2][i][j]));
			}
		}
		cout << max(ans,0ll) << "\n";
	}
	return void();
}
signed main () {
	ios::sync_with_stdio (false);
	cin.tie (0);
	cout.tie (0);
	int T;
	cin >> c >> T;
	while (T -- >0) solve ();
	return 0;
}