103322: [Atcoder]ABC332 C - T-shirts

Problem Statement

AtCoder Inc. sells T-shirts with its logo.

You are given Takahashi's schedule for $N$ days as a string $S$ of length $N$ consisting of 0, 1, and 2.
Specifically, for an integer $i$ satisfying $1\leq i\leq N$,

• if the $i$-th character of $S$ is 0, he has no plan scheduled for the $i$-th day;
• if the $i$-th character of $S$ is 1, he plans to go out for a meal on the $i$-th day;
• if the $i$-th character of $S$ is 2, he plans to attend a competitive programming event on the $i$-th day.

Takahashi has $M$ plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.

• On days he goes out for a meal, he will wear a plain or logo T-shirt.
• On days he attends a competitive programming event, he will wear a logo T-shirt.
• On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
• Once he wears a T-shirt, he cannot wear it again until he washes it.

Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the $N$ days. If he does not need to buy new T-shirts, print $0$.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.

Constraints

• $1\leq M\leq N\leq 1000$
• $S$ is a string of length $N$ consisting of 0, 1, and 2.
• $N$ and $M$ are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$S$

Output

Print the minimum number of T-shirts Takahashi needs to buy to be able to satisfy the conditions in the problem statement.
If he does not need to buy new T-shirts, print $0$.

Sample Input 1

6 1
112022

Sample Output 1

2

If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:

• On the first day, he wears a logo T-shirt to go out for a meal.
• On the second day, he wears a plain T-shirt to go out for a meal.
• On the third day, he wears a logo T-shirt to attend a competitive programming event.
• On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
• On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
• On the sixth day, he wears a logo T-shirt to attend a competitive programming event.

If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print $2$.

Sample Input 2

3 1
222

Sample Output 2

3

Sample Input 3

2 1
01

Sample Output 3

0

He does not need to buy new T-shirts.

问题描述

AtCoder Inc. 销售带有其徽标的T恤衫。

你会得到高桥君在 $N$ 天的日程安排，这是一个长度为 $N$ 的由 0、1 和 2 组成的字符串 $S$。

• 如果字符串 $S$ 的第 $i$ 个字符是 0，那么他第 $i$ 天没有计划；
• 如果字符串 $S$ 的第 $i$ 个字符是 1，那么他计划在第 $i$ 天出去吃饭；
• 如果字符串 $S$ 的第 $i$ 个字符是 2，那么他计划在第 $i$ 天参加编程比赛。

高桥君有 $M$ 件普通T恤衫，都在第一天开始前洗好并准备好了穿。此外，为了满足以下条件，他会买几件带有AtCoder徽标的T恤衫。

• 在他出去吃饭的那天，他会穿普通或带有徽标的T恤衫。
• 在他参加编程比赛的那天，他会穿带有徽标的T恤衫。
• 在他没有计划的那天，他不会穿任何T恤衫。此外，他会在那一刻洗掉所有穿过的T恤衫。从第二天开始，他可以再次穿上它们。
• 一旦他穿上一件T恤衫，他就不能在不洗的情况下再次穿上它。

确定高桥君需要购买的最少T恤衫数量，以便在 $N$ 天内的所有预定日期都能穿上合适的T恤衫。如果他不需要购买新T恤衫，打印 $0$。假设购买的T恤衫也在第一天开始前洗好并准备好使用。

约束条件

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

输入

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

$N$ $M$
$S$

输出

打印高桥君需要购买的最少T恤衫数量，以便满足问题描述中的条件。如果他不需要购买新T恤衫，打印 $0$。

样例输入1

6 1
112022

样例输出1

2

如果高桥君购买两件带有徽标的T恤衫，他可以按照以下方式穿T恤衫：

• 在第一天，他穿带有徽标的T恤衫出去吃饭。
• 在第二天，他穿普通T恤衫出去吃饭。
• 在第三天，他穿带有徽标的T恤衫参加编程比赛。
• 在第四天，他没有计划，所以他洗掉所有穿过的T恤衫。这使他能够在第一天、第二天和第三天再次使用穿过的T恤衫。
• 在第五天，他穿带有徽标的T恤衫参加编程比赛。
• 在第六天，他穿带有徽标的T恤衫参加编程比赛。

如果他购买一件或更少带有徽标的T恤衫，无论他如何使用，都无法满足条件。因此，打印 $2$。

样例输入2

3 1
222

样例输出2

3

样例输入3

2 1
01

样例输出3

0

他不需要购买新T恤衫。