1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define nl '\n'

using namespace std;
const int MAXN = 8001;
int prefix1[MAXN], prefix2[MAXN], prefix3[MAXN];
int n, k, t;

int check(int a, int b){
	//cerr<<a<<' '<<b<<nl;
	int skipped1 = prefix1[a+t-1] + prefix1[n] - prefix1[b-1];
	int skipped2 = prefix2[a+t-1] - prefix2[a-1] + prefix2[b+t-1] - prefix2[b-1];
	int skipped = skipped1 + skipped2;
	int house = prefix2[a] + prefix2[n] - prefix2[b+t-1];
	if(skipped > k) return -1;
	int res = n - b - t + a - house;
	int rem = min(k - skipped, house);
	//cerr<<res<<' '<<skipped<<' '<<house<<' '<<rem<<nl;
	res +=rem;
	return res;
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>k>>t;
	string s;
	cin>>s;
	for(int i=1; i<=n; i++){
		if(s[i-1] == '1'){
			prefix1[i]++;
		}
		if(s[i-1] == '2'){
			prefix2[i]++;
		}
		if(s[i-1] == '3'){
			prefix3[i]++;
		}
	}
	for(int i=1; i<=n; i++){
		prefix1[i] += prefix1[i-1];
		prefix2[i] += prefix2[i-1];
		prefix3[i] += prefix3[i-1];
	}
	int res = -1;
	if(prefix1[n] <= k){
		//int demand = k - prefix1[n];
		cout<<n - max(0, prefix1[n] + prefix2[n] - k)<<nl;
		return 0;
	}
	for(int a=1; a<=n - 2*t; a++){
		for(int b = a+t; b+t-1<=n; b++){
			res = max(res, check(a, b));
		}
	}
	cout<<res<<nl;
}