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
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define st first
#define nd second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

#ifdef LOCAL
#define DTP(x, y)                                    \
    auto operator<<(auto &o, auto a)->decltype(y, o) \
    {                                                \
        o << "(";                                    \
        x;                                           \
        return o << ")";                             \
    }
DTP(o << a.first << ", " << a.second, a.second);
DTP(for (auto i : a) o << i << ", ", all(a));
void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; }
#define debug(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x)
#else
#define debug(...) 42
#endif

void solve()
{
    int n, k, t;
    cin >> n >> k >> t;
    string S;
    cin >> S;
    vector<vi> DP(n + 1, vi(k + 1, 0)), DP1(n + 1, vi(k + 1, -INT_MAX)), DP2 = DP1;
    vi T(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        T[i] = T[i - 1];
        if (S[i - 1] != '3')
            T[i]++;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
        {
            if (S[i - 1] == '2')
            {
                DP[i][j] = DP[i - 1][j];
                if (j)
                    DP[i][j] = max(DP[i][j], DP[i - 1][j - 1] + 1);
            }
            else if (S[i - 1] == '1')
            {
                if (j)
                    DP[i][j] = DP[i - 1][j - 1] + 1;
                else
                    DP[i][j] = -INT_MAX;
            }
            else
                DP[i][j] = DP[i - 1][j] + 1;
        }
    // debug(T);
    for (int i = t; i <= n; i++)
        for (int j = 0; j <= k; j++)
        {
            // debug(i, j, T[i], T[i - t], i - t);
            if (j >= T[i] - T[i - t])
                DP1[i][j] = DP[i - t][j - T[i] + T[i - t]];
            DP1[i][j] = max(DP1[i][j], DP1[i - 1][j]);
        }
    for (int i = 2 * t; i <= n; i++)
        for (int j = 0; j <= k; j++)
        {
            if (j >= T[i] - T[i - t])
                DP2[i][j] = DP1[i - t][j - T[i] + T[i - t]];
            if (S[i - 1] == '3')
                DP2[i][j] = max(DP2[i][j], DP2[i - 1][j] + 1);
            else if (S[i - 1] == '2')
            {
                if (j)
                    DP2[i][j] = max(DP2[i][j], DP2[i - 1][j - 1] + 1);
                DP2[i][j] = max(DP2[i][j], DP2[i - 1][j]);
            }
            else
            {
                if (j)
                    DP2[i][j] = max(DP2[i][j], DP2[i - 1][j - 1] + 1);
            }
        }
    // for (auto &a : DP)
    //     debug(a);
    // for (auto &a : DP1)
    //     debug(a);
    // for (auto &a : DP2)
    //     debug(a);
    int ans = -INT_MAX;
    for (auto &a : DP.back())
        ans = max(a, ans);
    for (auto &a : DP2.back())
        ans = max(a, ans);
    cout << (ans < 0 ? -1 : ans) << endl;
}

main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int Z = 1;
    // cin >> Z;
    while (Z--)
        solve();
}