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
# n — liczba segment
# k — liczba spotkań, które może opuścić
# t — czas trwania przejazdu
#
# 1 — spotkanie w biurze
# 2 — zdalne spotkanie
# 3 — brak obowiązków

try:
    line1 = input().strip()
    if not line1:
        print(-1)

    parts = line1.split()
    if len(parts) != 3:
        print(-1)


    n = int(parts[0])
    k = int(parts[1])
    t = int(parts[2])

    if not (3 <= n <= 8000) or not (0 <= k <= n) or not (1 <= t < n):
        print(-1)


    s = input().strip()
    if len(s) != n or any(c not in {'1', '2', '3'} for c in s):
        print(-1)


except (ValueError, EOFError):
    print(-1)


prefix_1 = [0] * (n + 1)
prefix_2 = [0] * (n + 1)
prefix_3 = [0] * (n + 1)

for i in range(n):
    prefix_1[i + 1] = prefix_1[i] + (s[i] == '1')
    prefix_2[i + 1] = prefix_2[i] + (s[i] == '2')
    prefix_3[i + 1] = prefix_3[i] + (s[i] == '3')

max_tasks = -1

category1_missed = prefix_1[n]
if category1_missed <= k:
    allowed_miss_remote = k - category1_missed
    tasks_scenario1 = prefix_3[n] + min(allowed_miss_remote, prefix_2[n])
    max_tasks = tasks_scenario1

max_i = n - 2 * t
for i in range(max_i + 1):
    start_trip1 = i
    end_trip1 = i + t - 1
    if end_trip1 >= n:
        break
    missed_trip1 = (prefix_1[end_trip1 + 1] - prefix_1[start_trip1]) + (
                prefix_2[end_trip1 + 1] - prefix_2[start_trip1])

    for j in range(i + t, n - t + 1):
        start_trip2 = j
        end_trip2 = j + t - 1
        if end_trip2 >= n:
            break
        missed_trip2 = (prefix_1[end_trip2 + 1] - prefix_1[start_trip2]) + (
                    prefix_2[end_trip2 + 1] - prefix_2[start_trip2])

        missed_home1 = prefix_1[i]  # przed wyjazdem
        missed_home2 = prefix_1[n] - prefix_1[j + t]  # po powrocie

        total_fixed_misses = missed_home1 + missed_home2 + missed_trip1 + missed_trip2
        if total_fixed_misses > k:
            continue

        possible_miss_remote = (prefix_2[i] + (prefix_2[n] - prefix_2[j + t]))
        allowed_miss_remote = k - total_fixed_misses
        added_tasks = min(allowed_miss_remote, possible_miss_remote)

        tasks_home = prefix_3[i] + (prefix_3[n] - prefix_3[j + t])

        total_tasks = tasks_home + added_tasks
        if total_tasks > max_tasks:
            max_tasks = total_tasks

print(max_tasks if max_tasks != -1 else -1)