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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define mp make_pair
//~ #define r(x) resize(x)
//~ #define rf(x, c) resize(x, c)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define V vector
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
int add(int a, int b){return a+b >= mod ? a+b - mod : a+b;}
int sub(int a, int b){return a-b < 0 ? a-b + mod : a-b;}
int mul(int a, int b){return int(a * ll(b) % mod);}
int fpow(int a, ll b){
    int ret = 1;
    while(b){
        if(b & 1) ret = mul(ret, a);
        b >>= 1, a = mul(a, a);
    } return ret;
}
int inv(int a){ return fpow(a, mod-2); }
struct coeff{
    V<int> fac, invfac;
    coeff(int n){
        fac.resize(n+1), invfac.resize(n+1);
        fac[0] = 1, invfac[0] = 1;
        for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i-1], i);
        invfac[n] = inv(fac[n]);
        for(int i = n-1; i; --i) invfac[i] = mul(invfac[i+1], i+1);
    }
    int get(int n, int k){
        if(n < k) return 0;
        return mul(fac[n], mul(invfac[n-k], invfac[k]));
    }
};
void answer(){
    int n, k, T; scanf("%d%d%d\n", &n, &k, &T);
    V<int> t(n+2, 0);
    for(int i = 1; i <= n; ++i){
        char c; scanf("%c", &c);
        t[i] = c-'1'+1;
    }
    V<int> wpf(n+2, 0), wsf(n+2, 0);
    V<int> zpf(n+2, 0), zsf(n+2, 0);
    V<int> spf(n+2, 0), ssf(n+2, 0);
    for(int i = 1; i <= n; ++i){
        wpf[i] = wpf[i-1] + (t[i] == 3);
        zpf[i] = zpf[i-1] + (t[i] == 2);
        spf[i] = spf[i-1] + (t[i] == 1);
    }
    for(int i = n; i >= 1; --i){
        wsf[i] = wsf[i+1] + (t[i] == 3);
        zsf[i] = zsf[i+1] + (t[i] == 2);
        ssf[i] = ssf[i+1] + (t[i] == 1);
    }

    // for(int i = 1; i <= n; ++i) printf("%d %d\n", pf[i].fi, pf[i].se);
    
    int mx = -1;
    if(spf[n] <= k)
        mx = max(mx, wpf[n]+spf[n]+min(zpf[n], k-spf[n]));

    for(int i = T+1; i <= n-T; ++i){
        for(int j = i; j <= n-T; ++j){
            int pewne = wpf[i-T-1] + wsf[j+T+1] + spf[i-T-1] + ssf[j+T+1];
            int stracone = zpf[i-1]-zpf[i-T-1] + zsf[j+1]-zsf[j+T+1] +
                           spf[i-1] + ssf[j+1];
            int mozliwe = zpf[i-T-1] + zsf[j+T+1];
            if(stracone > k) continue;
            // printf("%d %d: %d %d %d\n", i, j, pewne, stracone, mozliwe);
            mx = max(mx, pewne+min(mozliwe, k-stracone));
        }
    }
    
    printf("%d\n", mx);
}
int main(){
		int T = 1;
		// scanf("%d", &T);
		//~ ios_base::sync_with_stdio(0); cin.tie(0); cin >> T;
		for(++T; --T; ) answer();
		return 0;
}