C - T-shirts Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

AtCoder 社はロゴ入りの T シャツを販売しています。

高橋君の N 日間の予定が 0, 1, 2 のみからなる長さ N の文字列 S で与えられます。
具体的には、1\leq i\leq N をみたす整数 i について、

  • S の i 文字目が 0 のとき、i 日目に何の予定も入っていません。
  • S の i 文字目が 1 のとき、i 日目に高橋君は食事に行く予定があります。
  • S の i 文字目が 2 のとき、i 日目に高橋君は競技プログラミングのイベントに行く予定が入っています。

高橋君は無地の T シャツを M 枚持っており、1 日目の直前の時点ですべて洗濯済みの状態となっています。
これに加えて、次の条件をみたすように行動できるように、高橋君は AtCoder のロゴ入りの T シャツを何枚か購入する事にしました。

  • 食事に行く日には、無地の T シャツ 1 枚またはロゴ入りの T シャツ 1 枚を着用する。
  • 競技プログラミングのイベントに行く日にはロゴ入りの T シャツ 1 枚を着用する。
  • 何の予定もない日には T シャツを着用しない。加えて、その時点で着用済みの T シャツを全て洗濯する。 洗濯した T シャツは翌日から着用できる。
  • 一度着用した T シャツは次に洗濯するまで着用できない。

N 日間のうち予定が入っている日すべてについて、条件をみたす T シャツを着用できるようにするために、高橋君は最低何枚のTシャツを購入する必要があるか求めてください。 新しく T シャツを購入する必要がないならば 0 を出力してください。
ただし、購入した T シャツも 1 日目の直前の時点ですべて洗濯済みの状態で存在するものとします。

制約

  • 1\leq M\leq N\leq 1000
  • S は 0, 1, 2 のみからなる長さ N の文字列
  • N,M は整数

入力

入力は以下の形式で標準入力から与えられる。

N M
S

出力

問題文の条件をみたすように行動するために 高橋君が購入する必要のある T シャツの枚数の最小値を出力せよ。
新しく購入する必要がないならば 0 を出力せよ。

入力例 1

6 1
112022

出力例 1

2

高橋君がロゴ入りの T シャツを 2 枚購入したとき、次のようにして高橋君は T シャツを着用することができます。

  • 1 日目、高橋君はロゴ入りの T シャツを着用して食事に行きます。
  • 2 日目、高橋君は無地の T シャツを着用して食事に行きます。
  • 3 日目、高橋君はロゴ入りの T シャツを着用して競技プログラミングのイベントに行きます。
  • 4 日目、高橋君は予定がないため、着用した T シャツをすべて洗濯します。これにより、1,2,3 日目に着用した T シャツを再び着用することが可能になります。
  • 5 日目、高橋君はロゴ入りの T シャツを着用して競技プログラミングのイベントに行きます。
  • 6 日目、高橋君はロゴ入りの T シャツを着用して競技プログラミングのイベントに行きます。

高橋君がロゴ入りの T シャツを 1 枚以下しか購入しなかった場合には、 どのようにしても条件をみたすように T シャツを着用することができません。
よって、2 を出力します。

入力例 2

3 1
222

出力例 2

3

入力例 3

2 1
01

出力例 3

0

高橋君は新しく T シャツを購入する必要はありません。

Score : 300 points

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.