题目描述

高桥有一个为期 $N$ 天的日程安排，用一个长度为 $N$ 的字符串 $S$ 表示。

其中:

• 如果第 $i$ 天的字符是 0，表示那天没有安排；
• 如果是 1，表示那天计划外出就餐；
• 如果是 2，表示那天计划参加编程比赛。

高桥有 $M$ 件普通T恤，在第一天之前都是洗好可以穿的。

为了满足以下条件，他还需要购买一些带 AtCoder 标志的T恤:

• 外出就餐时，他会穿普通T恤或带标志的T恤。
• 参加编程比赛时，他必须穿带标志的T恤。
• 没有安排的日子，他不会穿T恤。同时他会洗所有到那时为止穿过的T恤，从第二天开始可以再次穿这些T恤。
• 一件T恤穿过后，在洗之前不能再穿。

请计算高桥最少需要购买多少件带标志的T恤，才能在这 $N$ 天内满足所有条件。

如果不需要购买新T恤，输出 0。

输入格式

第一行输入两个整数 $N,M$。

第二行输入一个长度为 $N$ 的字符串 $S$。

输出格式

输出高桥需要购买的最少T恤数量。如果不需要购买新T恤，输出 0。

样例

6 1
112022

2

3 1
222

3

2 1
01

0

提示

样例说明 1

如果高桥购买两件带标志的T恤，他可以按以下方式穿T恤:

• 第一天，他穿一件带标志的T恤外出就餐。
• 第二天，他穿一件普通T恤外出就餐。
• 第三天，他穿一件带标志的T恤参加编程比赛。
• 第四天，他没有安排，所以他洗了所有穿过的T恤。这样他就可以重新使用第一、二、三天穿过的T恤。
• 第五天，他穿一件带标志的T恤参加编程比赛。
• 第六天，他穿一件带标志的T恤参加编程比赛。

样例说明 3

他不需要购买新的 T 恤。

数据范围

• $1\leq\ M\leq\ N\leq\ 1000$
• $S$ 只包含 0, 1, 2 且长度为 $N$ 的字符串
• $N,M$ 都是整数