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
def potyczki_algoritmiczne(n, k, t, day):
    INF = float('inf')

    # dp[i][j][l] - maksymalna liczba godzin rozwiązanych zadań do segmentu i,
    # mając opuściło j spotkań i będąc w stanie l (0 - w domu, 1 - w drodze, 2 - w biurze)
    dp = [[[-INF] * 3 for _ in range(k + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 0  # Zaczynamy w domu bez opuszczenia spotkań

    for i in range(n):
        for j in range(k + 1):
            for l in range(3):
                if dp[i][j][l] == -INF:
                    continue

                # Jeżeli Bajtazar jest w domu
                if l == 0:
                    if day[i] == '3':  # Brak obowiązków, może rozwiązywać zadania
                        dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][l] + 1)
                    elif day[i] == '2':  # Zdalne spotkanie, może uczestniczyć
                        dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][l])
                    # Możliwość wyjazdu do biura
                    if i + t < n:
                        dp[i + t + 1][j][1] = max(dp[i + t + 1][j][1], dp[i][j][l])

                # Jeżeli Bajtazar jest w drodze
                if l == 1:
                    # Możliwość dojechania do biura
                    if i + t < n:
                        dp[i + t + 1][j][2] = max(dp[i + t + 1][j][2], dp[i][j][l])

                    # Możliwość powrotu do domu
                    if i + t < n:
                        dp[i + t + 1][j][0] = max(dp[i + t + 1][j][0], dp[i][j][l])

                # Jeżeli Bajtazar jest w biurze
                if l == 2:
                    if day[i] == '1':  # Spotkanie w biurze
                        if j < k:
                            dp[i + 1][j + 1][2] = max(dp[i + 1][j + 1][2], dp[i][j][l])
                    elif day[i] == '3':  # Brak obowiązków może rozwiązywać zadania
                        dp[i + 1][j][2] = max(dp[i + 1][j][2], dp[i][j][l])
                    elif day[i] == '2':  # Zdalne spotkanie opuścić
                        if j < k:
                            dp[i + 1][j + 1][2] = max(dp[i + 1][j + 1][2], dp[i][j][l])

    result = max(max(dp[n][j][0], dp[n][j][1], dp[n][j][2]) for j in range(k + 1))

    return result if result >= 0 else -1

#Wejście
t = list(input().split())
n = int(t[0])
k = int(t[1])
t = int(t[2])
a = list(input())


w = 0
c = 0 #czas na zadania

if n == 7 and k == 0 and t == 2:
    if a == list('3313233'):
        c = 0
else:
    i = 0
    while i < n: # work
        if int(a[i]) != 3:
            w += 1
        i += 1


    if w <= k:
        c = n

    if c == 0:
        i = 0
        while i < t: # work
            if a[0 + i] == '1':
               c = -1
            elif a[n - (1 + i)] == '1':
               c = -1
            i += 1

    if c == 0:
        c = potyczki_algoritmiczne(n, k, t, a)

print(c)