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
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define ALL(x) begin(x), end(x)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define printBool(x) cout << ((x) ? "YES\n" : "NO\n")
#define printBoolR(x) {cout << ((x) ? "YES\n" : "NO\n"); return;}
inline ll nxt(){ll x;cin>>x;return x;}
#define fill_i(x) generate(ALL(x), nxt)

void testCase(int caseNr) {
    int n, k, t; cin >> n >> k >> t;
    k++;
    string s; cin >> s;
    vvvi DP(3, vvi(k, vi(n+1, -1e9)));
    DP[0][0][0] = 0;
    int next_t_meetings = 0;
    for (int i = 0; i < t; i++) if (s[i] != '3') next_t_meetings++;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            if (i + t <= n && j+next_t_meetings < k) {
                DP[1][j+next_t_meetings][i+t] = max(DP[1][j+next_t_meetings][i+t], DP[0][j][i]);
                DP[2][j+next_t_meetings][i+t] = max(DP[2][j+next_t_meetings][i+t], DP[1][j][i]);
            }
            if (s[i] == '1') {
                for (int x = 0; x < 3; x++) {
                    if (j+1 != k) DP[x][j+1][i+1] = max(DP[x][j+1][i+1], DP[x][j][i]+1);
                }
                DP[1][j][i+1] = max(DP[1][j][i+1], DP[1][j][i]);
            } else if (s[i] == '2') {
                for (int x = 0; x < 3; x++) {
                    if (j != k-1) DP[x][j+1][i+1] = max(DP[x][j+1][i+1], DP[x][j][i]+1);
                    DP[x][j][i+1] = max(DP[x][j][i+1], DP[x][j][i]);
                }
            } else {
                DP[0][j][i+1] = max(DP[0][j][i+1], DP[0][j][i]+1);
                DP[1][j][i+1] = max(DP[1][j][i+1], DP[1][j][i]);
                DP[2][j][i+1] = max(DP[2][j][i+1], DP[2][j][i]+1);
            }
        }
        if (s[i] != '3') next_t_meetings--;
        if (i+t < n && s[i+t] != '3') next_t_meetings++;
    }
    int best = -1;
    for (int j = 0; j < k; j++) best = max({best, DP[0][j][n], DP[2][j][n]});
    cout << best << '\n';
}

int main() {
    // freopen("input", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // int T; cin >> T; for (int t = 1; t <= T; t++) testCase(t);
    testCase(0);
    return 0;
}