Pracsiu Dan (dnprx) 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ța
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 ≤ n ≤ 1.000.0002 * 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.