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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <bitset>
#include <stack>
#include <string>
#include <cstring>
#include <cassert>
#include <limits.h>

using namespace std;

typedef unsigned long long LL;
typedef long double LD;

typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(VAR(i,a);i<=(b);++i)
#define FORD(i,a,b) for(VAR(i,a);i>=(b);--i)
#define FORE(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define VAR(a,b) __typeof(b) a=(b)
#define SIZE(a) ((int)((a).size()))
#define ALL(x) (x).begin(),(x).end()
#define CLR(x,a) memset(x,a,sizeof(x))
#define ZERO(x) memset(x,0,sizeof(x))
#define S(t,i) scanf("%" ## t, &i)
#define SI(i) scanf("%d", &i)

const int MAXN=8000+11;
char schedule[MAXN];
int w[MAXN], z[MAXN], b[MAXN], s[MAXN];
int nexts[MAXN];
int n, k, t;

int main() {
    ios_base::sync_with_stdio(0);
    SI(n);
    SI(k);
    SI(t);
    scanf(" ");
    FOR(i, 1, n) {
        scanf("%c", &schedule[i]);
        b[i] = b[i-1] + (schedule[i] == '1' ? 1 : 0);
        z[i] = z[i-1] + (schedule[i] == '2' ? 1 : 0);
        w[i] = w[i-1] + (schedule[i] == '3' ? 1 : 0);
        s[i] = b[i] + z[i];
    }
    // int nexti = n+1;
    // int nextval = -1;
    // FORD(i, n, 1) {
    //     if (nextval != s[i]) {
    //         nexti = i + 1;
    //         nextval = s[i];
    //     }
    //     nexts[i] = nexti;
    // }
    int result = -1;
    if (b[n] <= k) {
        if (k >= b[n] + z[n]) {
            result = n;
        } else {
            result = w[n] + k;
        }
    }

    if (s[n]-k<3000) {
    FOR(t1, 0, n-2*t-1) {
        int t2=t1+t;
        int t3 = t2+1;
        int t4 = t3 + t;
        while(t4 <= n) {
            int missed = b[t2] + (b[n] - b[t3]) + (z[t2] - z[t1]) + (z[t4] - z[t3]);
            if (k >= missed) {
                int wynik = w[t1] + b[t1] + (w[n] - w[t4]) + (b[n] - b[t4]) + min(k-missed, z[t1] + z[n] - z[t4]);
                result = max(result, wynik);
            }

            if (s[n]-k <= s[t3]-s[t2]) {
                break;
            }

            //t3 = nexts[t3];
            t3++;
            t4 = t3 + t;
        }
    }
    } else {
        FOR(t1, 0, n-2*t-1) {
            int t2=t1+t;
            int t3 = t2+1;
            int t4 = t3 + t;
            while(t4 <= n) {
                int missed = b[t2] + (b[n] - b[t3]) + (z[t2] - z[t1]) + (z[t4] - z[t3]);
                if (k >= missed) {
                    int wynik = w[t1] + b[t1] + (w[n] - w[t4]) + (b[n] - b[t4]) + min(k-missed, z[t1] + z[n] - z[t4]);
                    result = max(result, wynik);
                }

                // if (s[n]-k <= s[t3]-s[t2]) {
                //     break;
                // }

                //t3 = nexts[t3];
                t3++;
                t4 = t3 + t;
            }
        }
    }
    printf("%d\n", result);

    return 0;
}