Cerința

După ce Le Quack și-a pierdut toți banii dați de mama lui să cumpere pâine la Blackjack, acesta a decis să își creeze propriul joc de cărți unde își poate bate prietenii și să câștige banii înapoi. Jocul se joacă cu un pachet de N cărți. Pachetul de cărți este reprezentat că un șir binar cum va fi descris în cele ce urmează.Cărțile pot fi așezate pe față sau pe spate fără a conta culoarea sau valoarea cărții, pentru simplitate codificăm o care întoarsă prin cifra 0 și o carte pe față prin cifra 1 . Fiecare jucător poate face un număr nelimitat de operații de următorul tip: se alege un index i și se întorc toate cărțile din secvență de cărți i...n, adică o carte de valoare 0 se transformă în carte de valoare 1 și invers. Acum este rândul lui Le Quack, el va prezintă configurația curentă a cărților și voi trebuie să îl ajutați cu 2 cerințe, el va poate răsplăti cu un posibil loc I la concurs.

Cerinta 1: Stiind configuratia cartilor sunteti rugati sa aflati lungimea maxima a unei secvente de carti, astfel incat costul de a transforma aceasta secventa intr-o secventa de carti care contin doar valori de 1 este maxim K.

Certina 2: Stiind configuratia cartilor sunteti intrebati care este numarul secventelor de carti pentru care numarul minim de operatii pentru a devni o secventa care contine numai valori de 1 este fix K.

Date de intrare

Pe prima linie sunt scrise valorile C, N si K, reprezentand numarul cerintei, numarul de carti respectiv valoarea K descrisa in enunt. Pe a doua linie sunt N valori binare reprezentand sirul de carti. Numerele se citesc din fisierul flipc.in.

Date de ieșire

Se va tiparii un singur numar, reprezentand raspunul la cerinta aferenta. Numerele se tiparesc in fisieru flipc.out.

Restricții și precizări

• Pentru 40/40 p : N <= 1.000.000 , K <= N
• Pentru 30/40 p : N <= 200.000 , K <= N
• Pentru 10/40 p : N <= 10.000 , K <= min(N , 100)

• Pentru 60/60 p : N <= 1.000.000 , K <= N
• Pentru 50/60 p : N <= 200.000 , K <= N
• Pentru 15/60 p : N <= 10.000 , K <= min(N , 100)

• O carte NU se poate roti de 2 ori in aceasi mutare !

Exemplu:

flipc.in

1 5 2
10001

flipc.out

5

flipc.in

2 13 4
1010011111101

flipc.out

15

Explicație

Pentru primul exemplu : putem transforma tot stringul in valori de 1 in 2 operatii, prima operatie la
pozitia 2 si a doua la pozitia 5.

Pentru al doilea exemplu : niste exemple de secvente care contin doar valori de 1 si sunt formate prin
4 operatii ar avea capetele: {1,6}, {2,6}, {1,9} .....