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
// Catling
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
auto operator<<(auto&o,auto p)->decltype(p.first,o){return o<<'('<<p.first<<", "<<p.second <<')';}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<'{';int i=2;for(auto e:x)o<<(", ")+i<<e,i=0;return o<<'}';}
#define LOG(x...)cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x);
#else
#define LOG(x...)(void)0
#endif

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int, int> pii;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

#define all(x)  (x).begin(),(x).end()
#define endl    '\n'
#define size(x)  x.size()

const ll INF = 9223372036854775806;
const ll MAX_N = 1e9+1;
const ll MOD = 1e9+7; // 998244353

void solveTestCase() {
    int N, K, T;
    string S;
    cin >> N >> K >> T >> S;

    vector<int> firstPrefix(N + 1, 0), secondPrefix(N + 1, 0), thirdPrefix(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        firstPrefix[i + 1] = firstPrefix[i] + (S[i] == '1');
        secondPrefix[i + 1] = secondPrefix[i] + (S[i] == '2');
        thirdPrefix[i + 1] = thirdPrefix[i] + (S[i] == '3');
    }

    if (firstPrefix[N] + secondPrefix[N] <= K) {
        cout << N << endl;
        return;
    }

    int firstCaseTasks = -1;
    int firstTypeTotal = firstPrefix[N];
    if (firstTypeTotal <= K) {
        int availableSkips = K - firstTypeTotal;
        int possible_type2_skips = min(availableSkips, secondPrefix[N]);
        firstCaseTasks = thirdPrefix[N] + possible_type2_skips;
    }

    int secondMaxCase = -1;
    for (int s = 0; s <= N - 2 * T; ++s) {
        int A = s + T;
        for (int e = A; e <= N - T; ++e) {
            int firstPartHomeSkips = firstPrefix[s] + (firstPrefix[N] - firstPrefix[e + T]);
            int drivingSkips = (firstPrefix[s + T] - firstPrefix[s]) + (secondPrefix[s + T] - secondPrefix[s]) +
                                (firstPrefix[e + T] - firstPrefix[e]) + (secondPrefix[e + T] - secondPrefix[e]);

            if (firstPartHomeSkips + drivingSkips > K) continue;

            int thirdTypeInHome = (thirdPrefix[s] - thirdPrefix[0]) + (thirdPrefix[N] - thirdPrefix[e + T]);
            int secondTypeInHome = (secondPrefix[s] - secondPrefix[0]) + (secondPrefix[N] - secondPrefix[e + T]);
            int possibleSkips = K - (firstPartHomeSkips + drivingSkips);
            int totalTasks = thirdTypeInHome + min(secondTypeInHome, possibleSkips);

            secondMaxCase = max(secondMaxCase, totalTasks);
        }
    }

    int answerValue = max(firstCaseTasks, secondMaxCase);
    cout << (answerValue < 0 ? -1 : answerValue) << endl;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T = 1;

    while(T--) {
        solveTestCase();
    }
    return 0;
}