T 恤

题目描述

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

给你高桥接下来 $N$ 天的日程安排,用长度为 $N$、由 0、1、2 组成的字符串 $S$ 表示。

具体来说,对于满足 $1\le i\le N$ 的整数 $i$:

如果 $S$ 的第 $i$ 个字符是 0,则第 $i$ 天他没有安排;

如果 $S$ 的第 $i$ 个字符是 1,则第 $i$ 天他计划外出就餐;

如果 $S$ 的第 $i$ 个字符是 2,则第 $i$ 天他计划参加编程竞赛活动。

高桥在第一天前拥有 $M$ 件纯色 T 恤,均已洗净并可直接穿着。

此外,为了满足以下条件,他将购买若干件 AtCoder 标志 T 恤。

外出就餐的日子,他会穿纯色 T 恤或标志 T 恤。

参加编程竞赛活动的日子,他会穿标志 T 恤。

没有安排的日子,他不穿任何 T 恤。同时,他会清洗当天所有穿过的 T 恤。这些 T 恤从第二天起可以再次穿着。

一件 T 恤一旦穿过,在清洗之前不能再穿。

求在这 $N$ 天内,为了能在所有安排的日子里穿上合适的 T 恤,他最少需要购买多少件 T 恤。如果不需要购买新的 T 恤,则输出 $0$。

假设购买的 T 恤在第一天前也已洗净并可直接穿着。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$S$

输出格式

输出高桥为了满足题目所述条件所需购买的最少 T 恤件数。

如果不需要购买新的 T 恤,则输出 $0$。

样例

6 1
112022

2

如果高桥购买两件标志 T 恤,他可以按如下方式穿着:

第一天,他穿标志 T 恤外出就餐。

第二天,他穿纯色 T 恤外出就餐。

第三天,他穿标志 T 恤参加编程竞赛活动。

第四天,他没有安排,因此清洗了所有穿过的 T 恤。这样他就可以重新使用第一、二、三天穿过的 T 恤。

第五天,他穿标志 T 恤参加编程竞赛活动。

第六天,他穿标志 T 恤参加编程竞赛活动。

如果购买一件或更少的标志 T 恤,则无论如何都无法满足穿着条件。因此输出 $2$。

3 1
222

3

2 1
01

0

他不需要购买新的 T 恤。

数据范围

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