Score : $300$ points

问题描述

AtCoder Inc. 出售带有其标志的T恤衫。

您将得到高桥在 $N$ 天的日程安排，表示为一个长度为 $N$ 的字符串 $S$，由字符 0、1 和 2 组成。具体来说，对于满足 $1\leq i\leq N$ 的整数 $i$，

• 若第 $i$ 个字符为 0，则他在第 $i$ 天没有安排计划；
• 若第 $i$ 个字符为 1，他计划在第 $i$ 天外出就餐；
• 若第 $i$ 个字符为 2，他计划在第 $i$ 天参加一场编程竞赛活动。

高桥拥有 $M$ 件普通T恤，在第一天开始前都已清洗完毕并准备就绪。另外，为了能够满足以下条件，他打算购买几件带有 AtCoder 标志的 T 恤：

• 在外出就餐的日子里，他会穿一件普通或带有标志的 T 恤；
• 在参加编程竞赛活动的日子里，他会穿一件带有标志的 T 恤；
• 在没有计划的日子里，他不会穿任何 T 恤，并会洗掉当天所穿的所有 T 恤。从第二天起，他又可以再次穿着这些洗过的 T 恤；
• 一旦穿上一件 T 恤，除非洗过，否则不能再次穿着。

请确定他在 $N$ 天内需要购买至少多少件 T 恤才能确保在所有已安排日程中都能穿着合适的 T 恤。如果无需购买新 T 恤，则输出 $0$。 假设购买的 T 恤也在第一天开始前就已经清洗好并可直接使用。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 01:17:33