AT_abc332_c [ABC332C] T-shirts

AtCoder 社正在销售[带有 Logo 的 T 恤](https://suzuri.jp/AtCoder/5510290/t-shirt/s/ash)。 高桥君的 $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 恤，并且在第 $1$ 天开始前，这些 T 恤都已经洗净。 此外，为了能够满足以下条件，高桥君可以购买若干件带有 AtCoder Logo 的 T 恤： - 外出吃饭的日子，需要穿一件无印 T 恤或一件带 Logo 的 T 恤。 - 参加竞赛编程活动的日子，必须穿一件带 Logo 的 T 恤。 - 没有安排的日子不需要穿 T 恤，并且此时会把已经穿过的所有 T 恤都洗净。洗净后的 T 恤从第二天起可以再次穿。 - 一件 T 恤在下次洗净之前不能再次穿。 请计算，为了保证在 $N$ 天内所有有安排的日子都能满足上述条件，高桥君最少需要购买多少件带 Logo 的 T 恤。如果不需要购买新的 T 恤，则输出 $0$。 注意，新购买的 T 恤在第 $1$ 天开始前也都已经洗净。

输入以如下格式从标准输入读入： > $N$ $M$ $S$

请输出为了满足题目条件，高桥君最少需要购买的带 Logo 的 T 恤数量。如果不需要购买新的 T 恤，则输出 $0$。

## 限制条件 - $1 \leq M \leq N \leq 1000$ - $S$ 是一个仅包含 `0`、`1`、`2` 的长度为 $N$ 的字符串 - $N, M$ 均为整数 ## 样例解释 1 当高桥君购买了 $2$ 件带 Logo 的 T 恤时，可以如下安排穿着： - 第 $1$ 天，高桥君穿带 Logo 的 T 恤去吃饭。 - 第 $2$ 天，高桥君穿无印 T 恤去吃饭。 - 第 $3$ 天，高桥君穿带 Logo 的 T 恤去参加竞赛编程活动。 - 第 $4$ 天没有安排，因此将第 $1,2,3$ 天穿过的 T 恤全部洗净，可以再次穿。 - 第 $5$ 天，高桥君穿带 Logo 的 T 恤去参加竞赛编程活动。 - 第 $6$ 天，高桥君穿带 Logo 的 T 恤去参加竞赛编程活动。 如果高桥君只购买 $1$ 件或更少的带 Logo 的 T 恤，则无法满足所有条件。 因此，输出 $2$。 ## 样例解释 3 高桥君不需要购买新的 T 恤。 由 ChatGPT 4.1 翻译