题目描述

AtCoder公司售卖印有其品牌标识的T恤。

现给出高桥$N$天的日程安排，用仅由0、1、2组成的长度为$N$的字符串$S$表示。 具体来说，对于满足$1\leq i\leq N$的整数$i$：

• 若$S$的第$i$个字符为0，则高桥第$i$天无任何计划；
• 若$S$的第$i$个字符为1，则高桥第$i$天计划外出就餐；
• 若$S$的第$i$个字符为2，则高桥第$i$天计划参加算法竞赛活动。

高桥最初有$M$件素色T恤，在第一天开始前所有素色T恤均已洗净可穿。 此外，为满足以下穿着要求，他需要购买若干件印有AtCoder标识的品牌T恤：

1. 外出就餐时，他可穿素色T恤或品牌T恤；
2. 参加算法竞赛活动时，他必须穿品牌T恤；
3. 无计划的日子，他不穿任何T恤，且会将此前穿过的所有T恤全部洗净，洗净后的T恤从次日起可再次穿着；
4. 一件T恤一旦被穿上，需经清洗后方可再次穿着。

请你求出高桥为满足$N$天所有日程的穿着要求，最少需要购买多少件品牌T恤。若无需购买，输出$0$。 注意：购买的品牌T恤在第一天开始前也已洗净，可直接使用。

题目约束

• $1\leq M\leq N\leq 1000$
• $S$为仅由0、1、2组成的长度为$N$的字符串
• $N$和$M$均为整数

输入格式

输入数据从标准输入按以下格式给出：

$N$ $M$

$S$

输出格式

输出高桥满足所有穿着要求所需购买的品牌T恤的最小数量，若无需购买则输出$0$。

样例输入1

6 1
112022

样例输出1

2

样例解释1

若高桥购买2件品牌T恤，可按如下方式搭配穿着：

1. 第一天穿品牌T恤外出就餐；
2. 第二天穿素色T恤外出就餐；
3. 第三天穿品牌T恤参加算法竞赛；
4. 第四天无计划，将此前穿过的所有T恤洗净，这些T恤从第五天起可再次使用；
5. 第五天穿品牌T恤参加算法竞赛；
6. 第六天穿品牌T恤参加算法竞赛。

若购买的品牌T恤数量不超过1件，则无论如何搭配，都无法满足所有穿着要求，因此输出2。

样例输入2

3 1
222

样例输出2

3

样例输入3

2 1
01

样例输出3

0

样例解释3

高桥无需购买任何品牌T恤即可满足要求。