分数: 300 点
问题陈述
AtCoder Inc. 出售 带有其标志的T恤.
您将获得高桥的日程安排 N 天作为字符串 S 长度 N 组成 0, 1,和 2.
具体来说,对于整数 i 满意 1\leq i\leq N,
- 如果 i- 第一个字符 S is
0,他没有安排 i第一天; - 如果 i- 第一个字符 S is
1,他计划出去吃饭 i第一天; - 如果 i- 第一个字符 S is
2,他计划参加在 i第一天。
高桥有 M 纯色 T 恤,在第一天之前全部清洗并准备好穿着。
另外,为了能够满足以下条件,他会购买几件带有AtCoder标志的T恤。
- 出去吃饭的日子,他会穿素色或标志T恤。
- 在参加竞争性编程活动的日子里,他会穿一件带有徽标的 T 恤。
- 没有计划的日子里,他不会穿任何T恤。此外,他还会清洗当时穿过的所有 T 恤。从第二天开始,他可以再次佩戴它们。
- T 恤一旦穿过,就不能再穿,除非洗了。
确定他需要购买的最少 T 恤数量,以便能够在计划期间的所有预定日期穿着合适的 T 恤 N 天。如果他不需要购买新 T 恤,请打印 0.
假设购买的 T 恤在第一天之前也已清洗并可供使用。
约束
- 1\leq M\leq N\leq 1000
- S 是一个长度为的字符串 N 组成
0,1,和2. - N 和 M 是整数。
输入
输入由标准输入按以下格式给出:
N M S
输出
打印出 Takahashi 需要购买的最少 T 恤数量才能满足问题陈述中的条件。
如果他不需要购买新 T 恤,请打印 0.
样本输入 1
6 1 112022
示例输出 1
2
如果高桥买了两件标志T恤,他可以穿如下T恤:
- 第一天,他穿着logo T恤出去吃饭。
- 第二天,他穿着素色T恤出去吃饭。
- 第三天,他穿着标志T恤参加编程竞赛活动。
- 第四天,他没有计划,所以他把旧的T恤都洗了。这让他可以重复使用第一天、第二天和第三天穿的 T 恤。
- 第五天,他穿着标志T恤参加编程竞赛活动。
- 第六天,他穿着标志T恤参加编程竞赛活动。
如果他购买了一件或更少的徽标T恤,则无论如何他都不能使用T恤来满足条件。因此,打印 2.
示例输入 2
3 1 222
示例输出 2
3
示例输入 3
2 1 01
示例输出 3
0
他不需要购买新T恤。