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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef long double ld;
typedef unordered_map<int, int> umii;
typedef vector<pair<ll,ll>> vpll;
typedef tuple<int,int,int> tp;
const ll MOD = 1e9+696969;


int range(vi& p, int l, int r)
{
    if(l>r)return 0;
    return p[r]-p[l-1];
}

void solve()
{
    int n, k, t;
    cin >> n >> k >> t;

    string s;
    cin >> s;

    vi p1(n+1,0);
    vi p2(n+1,0);
    vi p3(n+1,0);  
    
    

    for(int i=1; i<=n; ++i)
    {
        char c=s[i-1];
        p1[i]=p1[i-1];
        p2[i]=p2[i-1];
        p3[i]=p3[i-1];

        if(c=='1')
        p1[i]++;
        else if(c=='2')
        p2[i]++;
        else if(c=='3')
        p3[i]++;

    }

    int notravel = -1000000000;
    int total1 = range(p1, 1, n);
    if(total1 <=k)
    {
        int total13 = range(p3,1,n);
        int total12 = range(p2, 1, n);
        notravel = total13 + total1 + min(total12, k-total1);
    }

    int best = -1000000000;
    for(int i=1; i<=n-2*t+1; ++i)
    {
        int l1 = range(p1,1,i-1);
        int l2 = range(p2,1,i-1);
        int l3 = range(p3,1,i-1);

        int road = range(p1, i, i+t-1) + range(p2, i, i+t-1);
        for(int j=i+t; j<=n-t+1; ++j)
        {
            int r1 = range(p1,j+t, n);
            int r2 = range(p2,j+t, n);
            int r3 = range(p3,j+t, n);

            int roadback= range(p1,j,j+t-1) + range(p2,j,j+t-1);

            int cost = road + roadback;

            int home1 = l1+r1;
            int home2 = l2+r2;
            int home3 = l3+r3;
            
            if(cost + home1 > k)continue;

            int extra = k-(cost+home1);
            int sl=min(home2, extra);

            int task = home3 + home1+sl;
            best = max(best, task);
        }

    }

    int ans = max(notravel, best);
    if(ans<0) ans=-1;
    cout << ans;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}