Molocoは、世界中の様々な企業がオンライン広告をより効果的に運用できるよう支援する広告技術企業です。Molocoの技術を用いることで、インターネットユーザーはより関連性の高い広告を目にすることができ、広告主は効果的に広告を配信することが可能になります。

ジョンソは、あるユーザーがホームページに合計 $2N$ 回訪問することを予測しており、ユーザーに対して「0番」の広告と「1番」の広告をそれぞれ $N$ 回ずつ表示したいと考えています。ホームページを訪問するたびに同じ種類の広告が続くと、ユーザーが広告に慣れてしまい広告効果が低下する可能性があるため、2種類の広告を適切に配置して広告効果を最大化しようとしています。

広告効果を定量的に把握するため、Molocoのエンジニアであるジョンソは「退屈さ」という指標を定義しました。$i \leq j$ に対して、$i$ 番目から $j$ 番目までの広告からなる区間の退屈さは、その区間内にある0番広告の個数と1番広告の個数の差の絶対値として定義されます。ユーザーが最終的に感じる退屈さは、すべての区間の退屈さの中での最大値です。

例えば、広告を 00110110 という順序で配置した場合、$3$ 番目の広告から $7$ 番目の広告までの退屈さは $|1 - 4| = 3$ です。この区間の退屈さが最大であるため、ユーザーが最終的に感じる退屈さも $3$ となります。

Molocoの優れたアルゴリズムによりユーザーのエンゲージメントを高める効果的な広告配置は見つかりましたが、ジョンソは「退屈さ」という指標がどれほど有効かを検証するために、この退屈さを減らそうと考えています。しかし、すでに広告の順序は決まっており、退屈さを減らすためには隣り合う2つの広告を入れ替える必要があり、そのたびに $1$ のコストがかかります。入れ替え操作は何度でも行うことができます。

ユーザーが最終的に感じる退屈さを $K$ 以下にするために必要な最小コストはいくらでしょうか。

入力

1行目に $N$ と $K$ が空白を挟んで与えられます。($1 \le K \le N \le 500\,000$)

2行目に、初期の広告配置を表す $N$ 個の 0 と $N$ 個の 1 からなる長さ $2N$ の文字列が与えられます。

出力

退屈さを $K$ 以下にするために必要な最小コストを出力してください。

与えられた広告順序の退屈さがすでに $K$ 以下である場合は 0 を出力します。

可能なすべての入力に対して、常に退屈さを $1$ にできることが証明できます。つまり、常に答えが存在します。

入出力例

入力 1

4 2
00110110

出力 1

1

入力 2

4 2
11110000

出力 2

3

入力 3

4 1
10011001

出力 3

2