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
// Author: Bartek Knapik

#include <cstdio>

const int MAX_N = 8000 + 9;

int n, k, t;
char input[MAX_N];
int cnt[3][MAX_N];

int _min(int a, int b) { return a < b ? a : b; }
int _max(int a, int b) { return a < b ? b : a; }

int solve(int ts, int te)
{
    int transfer_skip, office_skip, ans;
    
    transfer_skip = cnt[0][ts+t] - cnt[0][ts] + cnt[0][te+t] - cnt[0][te] + cnt[1][ts+t] - cnt[1][ts] + cnt[1][te+t] - cnt[1][te];
    office_skip = cnt[0][ts] - cnt[0][0] + cnt[0][n] - cnt[0][te+t];
    
    if (transfer_skip + office_skip > k) return -1;
    
    ans = cnt[2][ts] - cnt[2][0] + cnt[2][n] - cnt[2][te+t] + office_skip + _min(k - transfer_skip - office_skip, cnt[1][ts] - cnt[1][0] + cnt[1][n] - cnt[1][te+t]);
    
    return ans;
}

int solve()
{
    int tmp_ans, ans;
    
    int office_skip;
    
    office_skip = cnt[0][n];
    
    if (office_skip > k) ans = -1;
    else ans = cnt[0][n] + cnt[2][n] + _min(k - office_skip, cnt[1][n]);
    
    for (int ts = 0; ts < n; ++ts)
        for (int te = ts + t; te + t <= n; ++te)
        {
            tmp_ans = solve(ts, te);
            if (tmp_ans > ans) ans = tmp_ans;
        }
    
    return ans;
}

int main()
{
    scanf("%d%d%d", &n, &k, &t);
    scanf("%s", input);
    
    for (int i = 0; i < n; ++i)
    {
        cnt[0][i+1] = cnt[0][i];
        cnt[1][i+1] = cnt[1][i];
        cnt[2][i+1] = cnt[2][i];
        
        cnt[input[i]-'1'][i+1]++;
    }
    
    printf("%d\n", solve());
    
    return 0;
}