secvente

Se dau $n$ și $t$ două numere naturale nenule și $S$ un șir binar de $n$ elemente indexate de la $1$. O interschimbare în acest șir constă în alegerea a doi indici $i, j\ (1 ≤ i, j ≤ n)$ și schimbarea între ele a valorilor $S[i]$ și $S[j]$. O subsecvență de lungime $t$ a șirului $S$ reprezintă $t$ elemente aflate pe poziții consecutive în șirul $S$.

Cerință

Să se determine numărul minim de interschimbări ce trebuie realizate în șirul $S$ pentru a obține două subsecvențe disjuncte de lungime $t$ formate doar din elemente egale cu $1$.

Date de intrare

Pe prima linie a fișierului secvente.in se află separate printr-un spațiu numere $n$ și $t$. Pe a doua linie se află $n$ caractere 0 și 1.

Date de ieșire

Pe prima linie a fișierului de ieșire secvente.out se va afișa numărul minim de interschimbări necesare pentru obținerea a două subsecvențe disjuncte de lungime $t$ formate doar din elemente egale cu $1$. Dacă acest lucru este imposibil se va afișa -1.

Restricții și precizări

• $2 \leq n \leq 1\ 000\ 000$
• $2 \cdot t ≤ n$

Exemplul 1

secvente.in

7 2
1010101

secvente.out

2

Explicație

Elementul de pe poziția $1$ se interschimbă cu elementul de pe poziția $6$, iar elementul de pe poziția $3$ se interschimbă cu elementul de pe poziția $4$.

Exemplul 2

secvente.in

26 3
00010100100100010111001001

secvente.out

1

Explicație

O secvență convenabilă se situează între pozițiile $4$ și $6$ și alta între pozițiile $18$ și $20$. Este nevoie de o singură interschimbare pentru a pune un element de $1$ pe poziția $5$.