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
import sys

def solve():
    n, k, t = map(int, sys.stdin.readline().split())
    schedule = sys.stdin.readline().strip()
    
    INF = -10**9
    dp = [[[-INF] * (k + 1) for _ in range(3)] for _ in range(n + 1)]
    dp[0][0][0] = 0  # Start w domu, bez opuszczonych spotkań
    
    for i in range(n):
        for missed in range(k + 1):
            for loc in range(3):
                if dp[i][loc][missed] == INF:
                    continue
                
                # Opcja 1: Pozostanie w obecnej lokalizacji
                if loc == 0:  # W domu
                    dp[i + 1][0][missed] = max(dp[i + 1][0][missed], dp[i][0][missed] + (schedule[i] == '3'))
                elif loc == 2:  # W biurze
                    dp[i + 1][2][missed] = max(dp[i + 1][2][missed], dp[i][2][missed])
                
                # Opcja 2: Podróż do biura (jeśli Bajtazar zdąży wrócić)
                if loc == 0 and i + t + t <= n:
                    dp[i + t][1][missed] = max(dp[i + t][1][missed], dp[i][0][missed])
                
                # Opcja 3: Przybycie do biura po podróży
                if loc == 1 and i + 1 < n:
                    dp[i + 1][2][missed] = max(dp[i + 1][2][missed], dp[i][1][missed])
                
                # Opcja 4: Bajtazar może uczestniczyć w spotkaniu biurowym w czasie segmentu (n-t) i wrócić
                if loc == 2 and i == n - t:
                    dp[n][0][missed] = max(dp[n][0][missed], dp[i][2][missed])
                
                # Opcja 5: Powrót do domu (jeśli jest odpowiednio czasu)
                if loc == 2 and i + t + t <= n:
                    dp[i + t][1][missed] = max(dp[i + t][1][missed], dp[i][2][missed])
                
                # Opcja 6: Powrót do domu po podróży
                if loc == 1 and i + 1 < n:
                    dp[i + 1][0][missed] = max(dp[i + 1][0][missed], dp[i][1][missed])
                
                # Opcja 7: Opuszczenie spotkania, jeśli to dozwolone
                if (schedule[i] == '1' or schedule[i] == '2') and missed < k:
                    dp[i + 1][loc][missed + 1] = max(dp[i + 1][loc][missed + 1], dp[i][loc][missed])
    
    result = max(dp[n][0])  # Maksymalna liczba godzin rozwiązywania zadań w domu po poprawnym powrocie
    
    print(-1 if result == INF else result)

if __name__ == "__main__":
    solve()