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
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=8e3+5,INF=1e8;
int n,m,k;
string s;
int f[N][N],g[N][N],h[N][N];
signed main(){
    cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m>>k>>s,s=" "+s;
	for(int i=0;i<=n;++i)
		for(int j=0;j<=m;++j)
			f[i][j]=(i?-INF:0),g[i][j]=-INF,h[i][j]=-INF;
	for(int i=0;i<n;++i){
		if(i+k<=n){
			int r=0;
			for(int j=i+1;j<=i+k;++j)if(s[j]!='3')++r;
			for(int j=0;j+r<=m;++j)
				g[i+k][j+r]=max(g[i+k][j+r],f[i][j]),h[i+k][j+r]=max(h[i+k][j+r],g[i][j]);
		}
		if(s[i+1]=='1'){
			for(int j=0;j<=m;++j)
				f[i+1][j]=max(f[i+1][j],(j?f[i][j-1]+1:-INF)),
				g[i+1][j]=max(g[i+1][j],g[i][j]),
				h[i+1][j]=max(h[i+1][j],(j?h[i][j-1]+1:-INF));
		}
		else if(s[i+1]=='2'){
			for(int j=0;j<=m;++j)
				f[i+1][j]=max(f[i+1][j],max(f[i][j],(j?f[i][j-1]+1:-INF))),
				g[i+1][j]=max(g[i+1][j],g[i][j]),
				h[i+1][j]=max(h[i+1][j],max(h[i][j],(j?h[i][j-1]+1:-INF)));
		}
		else{
			for(int j=0;j<=m;++j)
				f[i+1][j]=max(f[i+1][j],f[i][j]+1),
				g[i+1][j]=max(g[i+1][j],g[i][j]),
				h[i+1][j]=max(h[i+1][j],h[i][j]+1);
		}
	}
	cout<<max(-1,max(f[n][m],h[n][m]))<<'\n';
	return 0;
}
/*
*/