Moloco to firma zajmująca się technologią reklamową, która pomaga różnym firmom na całym świecie skuteczniej prowadzić reklamy online. Dzięki technologii Moloco użytkownicy internetu widzą bardziej dopasowane reklamy, a reklamodawcy mogą skuteczniej docierać do odbiorców.

Jongseo przewidział, że użytkownik odwiedzi stronę internetową łącznie $2N$ razy i chce wyświetlić mu łącznie $N$ reklam typu 0 oraz $N$ reklam typu 1. Ponieważ ciągłe wyświetlanie tego samego rodzaju reklamy przy każdej wizycie może sprawić, że użytkownicy przyzwyczają się do nich, co obniży skuteczność reklam, Jongseo chce rozmieścić oba rodzaje reklam tak, aby zmaksymalizować efekt reklamowy.

Aby ilościowo określić skuteczność reklam, inżynierowie Moloco zdefiniowali wskaźnik zwany „nudą”. Dla $i \leq j$, nuda przedziału składającego się z reklam od $i$-tej do $j$-tej jest zdefiniowana jako różnica między liczbą reklam typu 0 a liczbą reklam typu 1 w tym przedziale. Nuda, którą ostatecznie odczuwa użytkownik, to wartość maksymalna spośród nudy wszystkich możliwych przedziałów.

Na przykład, jeśli reklamy są rozmieszczone w kolejności 00110110, nuda od 3. do 7. reklamy wynosi $|1 - 4| = 3$. Ponieważ jest to przedział o największej nudzie, nuda odczuwana przez użytkownika również wynosi 3.

Dzięki świetnym algorytmom Moloco udało się znaleźć skuteczne rozmieszczenie reklam zwiększające zaangażowanie użytkowników, jednak Jongseo chce zmniejszyć nudę, aby sprawdzić, jak dobrze działa ten wskaźnik. Ponieważ kolejność reklam jest już ustalona, aby zmniejszyć nudę, można zamieniać miejscami dwie sąsiadujące ze sobą reklamy, co kosztuje 1 jednostkę kosztu. Operację zamiany można wykonywać dowolną liczbę razy.

Jaki jest minimalny koszt potrzebny na to, aby nuda odczuwana przez użytkownika wynosiła co najwyżej $K$?

Wejście

W pierwszej linii podane są liczby $N$ oraz $K$ oddzielone spacją ($1 \le K \le N \le 500\,000$).

W drugiej linii podany jest ciąg znaków o długości $2N$, składający się z $N$ zer i $N$ jedynek, reprezentujący początkowe rozmieszczenie reklam.

Wyjście

Wypisz minimalny koszt potrzebny na to, aby nuda wynosiła co najwyżej $K$.

Jeśli nuda w podanej kolejności reklam jest już mniejsza lub równa $K$, wypisz 0.

Można wykazać, że dla każdego możliwego wejścia zawsze można osiągnąć nudę równą 1. Oznacza to, że rozwiązanie zawsze istnieje.

Przykład

Wejście 1

4 2
00110110

Wyjście 1

1

Wejście 2

4 2
11110000

Wyjście 2

3

Wejście 3

4 1
10011001

Wyjście 3

2