지루함 줄이기

Moloco는 전 세계 여러 회사가 온라인 광고를 더 효과적으로 운영하도록 돕는 광고 기술 회사입니다. Moloco의 기술을 사용하면 인터넷 사용자는 더 관련성 높은 광고를 보고, 광고주는 광고를 효과적으로 낼 수 있습니다.

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

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

예를 들어 광고를 00110110 순서로 배치하면, 3번째 광고부터 7번째 광고까지 구간의 지루함은 $|1-4|=3$입니다. 이 구간의 지루함이 가장 크므로, 유저가 최종적으로 느끼는 지루함도 3입니다.

종서는 "지루함" 지표가 얼마나 잘 작동하는지 알아보려고 지루함을 줄이려 합니다. 다만 광고 순서는 이미 정해져 있어, 지루함을 줄이려면 연달아 나오는 두 광고를 맞바꾸는 데 1만큼의 비용을 써야 합니다. 맞바꾸는 작업은 원하는 만큼 할 수 있습니다.

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

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

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

지루함을 $K$ 이하로 만드는 데 필요한 최소 비용을 출력합니다.

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

어떤 입력에 대해서도 지루함을 $1$로 만들 수 있음을 보일 수 있습니다. 즉, 답은 항상 존재합니다.