你正悠闲地走着，突然遭到了一群野生宝可梦的伏击。这个世界是一个包含 $N$ 列的网格，列编号从 $1$ 到 $N$，每只宝可梦都分布在其中某一列中，企图困住你。但你早有准备，你带来了你忠实的卡比兽（Snorlax），它懂得使用宝可梦界最强大的招式之一：认真起来大爆击（Pulverizing Pancake）。当使用这个招式时，卡比兽会冲向任意一列，击败该列路径上的所有宝可梦。

毁灭的活化身

它的冲击力如此之大，以至于相邻列的宝可梦会被推到更外侧的一列。例如，如果卡比兽冲向第 $3$ 列，第 $3$ 列的宝可梦将被击败，第 $2$ 列的任何宝可梦将被推到第 $1$ 列（但不会被击败），第 $4$ 列的任何宝可梦将被推到第 $5$ 列。这种推动效果总是会发生，除非被推动的宝可梦将超出世界的第一列或最后一列（即卡比兽冲向第 $2$ 列或第 $N - 1$ 列），在这种情况下，对应相邻列的宝可梦不会移动（因为没有可以容纳它们的列）。该效果仅发生在与卡比兽相邻的两列上，不会在整个网格中产生链式反应。

你的卡比兽使用这个强大招式的次数是有限的，因此你希望在击败所有宝可梦的前提下，最小化使用该招式的次数。每次使用该招式时，你可以选择卡比兽冲向的任意一列（包括没有宝可梦的列）。计算卡比兽最少需要使用多少次“认真起来大爆击”才能击败所有野生宝可梦。

输入格式

输入第一行包含两个空格分隔的整数 $N$ 和 $M$。这分别表示世界中的列数（$1 \le N \le 10^5$）和有野生宝可梦的列数（$0 \le M \le N$）。

第二行包含一个由 $N$ 个 1 和 0 组成的字符串 $a_1 a_2 \dots a_N$，其中如果第 $i$ 列有野生宝可梦，则 $a_i$ 为 1，否则为 0。

输出格式

输出单行，包含卡比兽击败所有野生宝可梦所需使用“认真起来大爆击”的最少次数。

样例

输入样例 1

3 3
111

输出样例 1

2

输入样例 2

6 5
110111

输出样例 2

4