Moloco est une entreprise de technologie publicitaire qui aide diverses sociétés à travers le monde à améliorer leurs campagnes publicitaires en ligne. Grâce à la technologie de Moloco, les internautes voient des publicités plus pertinentes et les annonceurs peuvent diffuser leurs publicités de manière efficace.

Jongseo a prédit qu'un utilisateur visitera une page web un total de $2N$ fois, et il souhaite montrer à l'utilisateur deux types de publicités, le type 0 et le type 1, $N$ fois chacun. Si le même type de publicité est affiché continuellement à chaque visite, les utilisateurs peuvent s'y habituer, ce qui réduit l'efficacité publicitaire. Par conséquent, il souhaite maximiser l'efficacité en organisant judicieusement les deux types de publicités.

Afin de mesurer quantitativement l'efficacité publicitaire, l'ingénieur de Moloco, Jongseo, a défini un indicateur appelé « ennui ». Pour $i \leq j$, l'ennui d'un intervalle composé des publicités allant de la $i$-ième à la $j$-ième est défini comme la différence absolue entre le nombre de publicités de type 0 et le nombre de publicités de type 1 dans cet intervalle. L'ennui ressenti par l'utilisateur est la valeur maximale de l'ennui parmi tous les intervalles possibles.

Par exemple, si les publicités sont disposées dans l'ordre 00110110, l'ennui de l'intervalle allant de la $3$-ième à la $7$-ième publicité est $|1 - 4| = 3$. Comme cet intervalle présente l'ennui le plus élevé, l'ennui final ressenti par l'utilisateur est également $3$.

Grâce aux excellents algorithmes de Moloco, une disposition efficace des publicités permettant d'augmenter l'engagement des utilisateurs a été trouvée. Cependant, Jongseo souhaite réduire l'ennui afin de tester la pertinence de cet indicateur. Comme l'ordre des publicités est déjà fixé, pour réduire l'ennui, il est nécessaire d'échanger deux publicités adjacentes, ce qui coûte $1$ unité. Cette opération d'échange peut être effectuée autant de fois que souhaité.

Quel est le coût minimal nécessaire pour que l'ennui final ressenti par l'utilisateur soit inférieur ou égal à $K$ ?

Entrée

La première ligne contient $N$ et $K$ séparés par un espace ($1 \le K \le N \le 500\,000$).

La deuxième ligne contient une chaîne de caractères de longueur $2N$ composée uniquement de $N$ caractères 0 et $N$ caractères 1, représentant la disposition initiale des publicités.

Sortie

Affichez le coût minimal nécessaire pour rendre l'ennui inférieur ou égal à $K$.

Si l'ennui de la disposition donnée est déjà inférieur ou égal à $K$, affichez 0.

Il est possible de démontrer que pour toute entrée donnée, il est toujours possible de rendre l'ennui égal à $1$. En d'autres termes, une solution existe toujours.

Exemples

Entrée 1

4 2
00110110

Sortie 1

1

Entrée 2

4 2
11110000

Sortie 2

3

Entrée 3

4 1
10011001

Sortie 3

2