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
from sys import stdin, stdout


def count_periods(start, end, activity_type):
    return activity_counter[activity_type][end] - activity_counter[activity_type][start]


def get_case_value(dojazd, powrot):
    """
    dojazd - first time period when riding to the office
    powrot - first time period when riding home
    counting from 0
    """
    zdalne_zgubione = count_periods(dojazd, dojazd + t, 2) + count_periods(powrot, powrot + t, 2)
    biurowe_zgubione = count_periods(0, dojazd + t, 1) + count_periods(powrot, n, 1)
    zgubione = zdalne_zgubione + biurowe_zgubione
    if zgubione > k:
        return -1
    zdalne_domowe = count_periods(0, dojazd, 2) + count_periods(powrot + t, n, 2)
    czas_domowy = dojazd + n - powrot - t
    do_odbycia_dom = max(0, zdalne_domowe + zgubione - k)
    return czas_domowy - do_odbycia_dom


def get_no_office():
    """
    jaki wynik, jeśli w ogóle nie jedzie do biura
    """
    zgubione = count_periods(0, n, 1)
    if zgubione > k:
        return -1
    zdalne_domowe = count_periods(0, n, 2)
    do_odbycia_dom = max(0, zdalne_domowe + zgubione - k)
    return n - do_odbycia_dom


def brute_force():
    output = get_no_office()
    for dojazd in range(0, n - 2*t):
        for powrot in range(dojazd + t + 1, n - t + 1):
            output = max(output, get_case_value(dojazd, powrot))
    return output


def solve():
    zysk_start = [-1] * (k + 1)
    max_nieznany = k
    dojazd = n - 2*t - 1
    while dojazd >= 0:
        koszt = count_periods(0, dojazd + t, 2) + count_periods(0, dojazd + t, 1)
        zysk = dojazd
        zdalne_domowe = count_periods(0, dojazd, 2)
        min_koszt = koszt - zdalne_domowe
        i = min(max_nieznany, koszt)
        # print(dojazd, koszt, zysk, min_koszt)
        while i >= min_koszt:
            zysk_start[i] = zysk - koszt + i
            i -= 1
        # print(zysk_start)
        max_nieznany = min(min_koszt - 1, max_nieznany)
        dojazd -= 1

    zysk_koniec = [-1] * (k + 1)
    max_nieznany = k
    powrot = t + 1
    while powrot <= n - t:
        koszt = count_periods(powrot, n, 2) + count_periods(powrot, n, 1)
        zysk = n - powrot - t
        zdalne_domowe = count_periods(powrot + t, n, 2)
        min_koszt = koszt - zdalne_domowe
        i = min(max_nieznany, koszt)
        while i >= min_koszt:
            zysk_koniec[i] = zysk - koszt + i
            i -= 1
        max_nieznany = min(min_koszt - 1, max_nieznany)
        powrot += 1

    output = get_no_office()
    for i in range(0, k+1):
        zs = zysk_start[i]
        zk = zysk_koniec[k-i]
        if (zs >= 0) and (zk >= 0):
            output = max(output, zs + zk)

    # print(zysk_start)
    # print(zysk_koniec)
    return output


n, k, t = [int(s) for s in stdin.readline().split()]
activities_str = stdin.readline().strip()

activity_counter = {i: [0] for i in range(1, 4)}
for s in activities_str:
    for i in range(1, 4):
        activity_counter[i].append(activity_counter[i][-1])
    activity_counter[int(s)][-1] += 1

output = solve()
stdout.write(str(output))