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
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("O0")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

#define pb push_back
#define F first
#define S second
#define ll long long
#define ld double long
#define ull unsigned long long
#define endl '\n'


const ll N = 3e5 + 36;
const ll M = 2e3 + 36;
const ll INF = 1e9 + 7;
const ll MOD = 1e9 + 7;
const ll MOD1 = 888888901;
const ll MOD2 = 999988901;
const ll X[8] = {1, -1, 2, 2, -2, -2, 1, -1};
const ll Y[8] = {2, 2, 1, -1, 1, -1, -2, -2};
const ld PI = 3.14159265358979323846;
const ld EPS = 1e-10;

//tree < pair < string, int >, null_type, less < pair < string, int > >, rb_tree_tag, tree_order_statistics_node_update > a;

//mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
mt19937 gen(19937);


signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL
    int n, k, t;
    cin >> n >> k >> t;
    string s;
    cin >> s;
    vector<int> pref[3];
    for (int i(0); i < 3; ++i){
       pref[i].resize(n + 1, 0);
    }
    for (int i(0); i < n; ++i) {
       if (i != 0) {
         for (int j(0); j < 3; ++j) {
            pref[j][i] = pref[j][i - 1];
         }
       }
       ++pref[s[i] - '1'][i];
    }
    int ans = -1;
    for (int i(0); i < n - t; ++i) {
       for (int j(i + t); j <= n - t; ++j) {
         int missed = 0, sum = 0, possible = 0, mishome = 0;
         if (i) {
            missed += pref[0][i - 1];
            mishome = pref[0][i - 1];
            sum += pref[2][i  - 1];
            possible += pref[1][i - 1];
            missed += pref[0][i + t - 1] - pref[0][i - 1];
            missed += pref[1][i + t - 1] - pref[1][i - 1];
         } else {
            missed += pref[0][i + t - 1];
            missed += pref[1][i + t - 1];
         }
         
         missed += pref[0][j + t - 1] - pref[0][j - 1];
         missed += pref[1][j + t - 1] - pref[1][j - 1];
         {
            missed += pref[0][n - 1] - pref[0][j + t - 1];
            mishome += pref[0][n - 1] - pref[0][j + t - 1];
            sum += pref[2][n - 1] - pref[2][j + t - 1];
            possible += pref[1][n - 1] - pref[1][j + t - 1];
         }
         
         if (missed <= k) {
            ans = max(ans, sum + mishome + min(possible, k - missed));
         }
       }
    }
    
    if (k >= pref[0][n - 1]) {
       ans = max(ans, pref[2][n - 1] + min(k, pref[1][n - 1] + pref[0][n - 1]));
    }
    
    cout << ans << endl;
    
    return 0;
}