← 返回题目列表

AtCoder · abc332_c

E. T 恤

中文机器翻译题面 查看原题

分数: 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恤。