지루함 줄이기

Moloco는 전 세계의 다양한 회사들이 온라인 광고를 더 잘할 수 있도록 돕는 광고 기술 회사입니다. Moloco의 기술을 사용하면 인터넷 사용자들이 더 관련성 높은 광고를 볼 수 있게 되고, 광고주들은 효과적으로 광고를 할 수 있습니다.

종서는 유저가 한 홈페이지에 총 $2N$번 방문할 것을 예측하였고, 유저에게 0번 광고와 1번 광고 총 두 종류의 광고를 각각 $N$번씩 보여주고자 합니다. 홈페이지를 방문할 때마다 같은 종류의 광고가 계속 나오면 사람들이 광고에 익숙해져 광고 효과가 떨어질 수 있기 때문에, 두 가지의 광고를 잘 배치하여 광고 효과를 극대화하고자 합니다.

광고 효과를 정량적으로 파악하기 위해 Moloco의 엔지니어 종서는 “지루함”이라는 지표를 정의했습니다. $i\leq j$에 대해, $i$번째부터 $j$번째까지의 광고로 이루어진 구간의 지루함은 구간 내에 있는 0번 광고의 개수와 1번 광고의 개수의 차이로 정의됩니다. 유저가 최종적으로 느끼는 지루함은 모든 구간의 지루함 중 최댓값입니다.

예를 들어, 광고를 00110110과 같은 순서로 배치하였을 때, $3$번째 광고부터 $7$번째 광고까지의 지루함은 $|1-4|=3$입니다. 이 구간이 지루함이 가장 크기 때문에, 유저가 최종적으로 느끼는 지루함 역시 $3$입니다.

Moloco의 훌륭한 알고리즘을 통해 유저의 참여도를 높일 수 있는 효과적인 광고 배치를 알아냈으나, 종서는 “지루함”이라는 지표가 얼마나 잘 작동하는지를 알아보기 위해 지루함을 줄이려고 합니다. 그러나 이미 광고의 순서가 정해져, 지루함을 줄이기 위해서는 연달아 나오는 두 광고를 맞바꾸기 위해 $1$만큼의 비용을 소모해야만 합니다. 맞바꾸는 작업은 원하는 만큼 수행할 수 있습니다.

유저가 최종적으로 느끼는 지루함을 $K$ 이하로 만드는 데 필요한 최소 비용은 얼마일까요?

첫 줄에 $N$과 $K$가 공백을 사이에 두고 주어집니다. ($1\le K\le N\le 500\\, 000$)

둘째 줄에는 초기 광고 배치를 나타내는 $N$개의 0과 $N$개의 1로만 이루어진 길이가 $2N$인 문자열이 주어집니다.

지루함을 $K$ 이하로 만들기 위해서 필요한 최소 비용을 출력합니다.

주어진 광고 순서의 지루함이 이미 $K$ 이하인 경우 0을 출력합니다.

가능한 모든 입력에 대해 항상 지루함을 $1$로 만들 수 있음을 보일 수 있습니다. 즉, 항상 답이 존재합니다.