问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and will generate a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program.
### Question:
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.

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.

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.

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.

### Format: Read the inputs from stdin solve the problem and write the answer to stdout (do not directly test on the sample inputs). Enclose your code within delimiters as follows.
```python
# YOUR CODE HERE
```

### Answer: (use the provided format with backticks)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
import sys

def solve():
n, m = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().strip()

logo_needed = 0
plain_available = m
logo_used = 0

for day in s:
if day == '0':
# On days with no plans, reset the count of available plain T-shirts
plain_available = m
logo_used = 0
elif day == '1':
# On days he goes out for a meal, use a plain T-shirt if available
if plain_available > 0:
plain_available -= 1
else:
# If no plain T-shirts are available, use a logo T-shirt
logo_used += 1
logo_needed = max(logo_needed, logo_used)
elif day == '2':
# On days he attends a competitive programming event, use a logo T-shirt
logo_used += 1
logo_needed = max(logo_needed, logo_used)

print(logo_needed)

if __name__ == '__main__':
solve()
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
deepseek-r1

```python
n, m = map(int, input().split())
s = input().strip()

segments = []
current = []
for c in s:
if c == '0':
if current:
segments.append(current)
current = []
else:
current.append(c)
if current:
segments.append(current)

max_logo = 0
for seg in segments:
num_2 = sum(1 for c in seg if c == '2')
num_1 = len(seg) - num_2
required = num_2 + max(0, num_1 - m)
max_logo = max(max_logo, required)

print(max_logo)
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
N, M = map(int, input().split())
S = input().strip()

K_logo_needed_overall = 0
K1 = 0
K2 = 0

for i in range(N):
if S[i] == '0':
K_logo_needed_in_segment = K2 + max(0, K1 - M)
K_logo_needed_overall = max(K_logo_needed_overall, K_logo_needed_in_segment)
K1 = 0
K2 = 0
else:
if S[i] == '1':
K1 += 1
elif S[i] == '2':
K2 += 1

# Process the last segment if it doesn't end with '0'
K_logo_needed_in_segment = K2 + max(0, K1 - M)
K_logo_needed_overall = max(K_logo_needed_overall, K_logo_needed_in_segment)

print(K_logo_needed_overall)
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
gpt-4o-2024-08-06 ```python
# YOUR CODE HERE
def min_tshirts_to_buy(N, M, S):
plain_available = M
logo_available = 0
logo_needed = 0

for i in range(N):
if S[i] == '1':
# He can wear either a plain or a logo T-shirt
if plain_available > 0:
plain_available -= 1
elif logo_available > 0:
logo_available -= 1
else:
# If no plain or logo T-shirts are available, he needs to buy a logo T-shirt
logo_needed += 1
elif S[i] == '2':
# He must wear a logo T-shirt
if logo_available > 0:
logo_available -= 1
else:
# If no logo T-shirts are available, he needs to buy a logo T-shirt
logo_needed += 1

# On days with no plans, he washes all T-shirts
if S[i] == '0':
plain_available = M
logo_available += logo_needed
logo_needed = 0

return logo_needed

# Read input
import sys
input = sys.stdin.read
data = input().strip().split()
N = int(data[0])
M = int(data[1])
S = data[2]

# Calculate and print the result
result = min_tshirts_to_buy(N, M, S)
print(result)
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
DeepSeek-Coder-V2-Lite-Instruct ```python
# YOUR CODE HERE
def min_shirts_to_buy(N, M, S):
# Initialize the number of logo T-shirts needed
logo_shirts = 0
# Initialize a list to keep track of the days when each shirt is last worn
last_worn = [-1] * (N + 1)
# Initialize a list to keep track of the available plain shirts
plain_shirts = [1] * (N + 1)

for i in range(N):
if S[i] == '1':
# Find the most recent available plain shirt
for j in range(1, M + 1):
if last_worn[j] < i - j:
# Use this plain shirt
last_worn[j] = i
break
else:
# If no plain shirt is available, buy a new logo shirt
logo_shirts += 1
last_worn[M + logo_shirts] = i
elif S[i] == '2':
# Always wear a logo shirt for competitive programming events
logo_shirts += 1
last_worn[M + logo_shirts] = i
# No action needed for '0' as he doesn't wear any shirts on that day

return logo_shirts

# Read input from stdin
import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
M = int(data[1])
S = data[2]

# Solve the problem and print the result
print(min_shirts_to_buy(N, M, S))
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
Meta-Llama-3.1-405B-Instruct-Turbo ```python
import sys

def solve():
n, m = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().strip()

cnt = 0
plain = m
logo = 0
max_logo = 0
for i in range(n):
if s[i] == '0':
plain = m
logo = 0
elif s[i] == '1':
if plain > 0:
plain -= 1
else:
logo += 1
max_logo = max(max_logo, logo)
else:
logo += 1
max_logo = max(max_logo, logo)

print(max_logo)

if __name__ == '__main__':
solve()
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
Meta-Llama-3.1-70B-Instruct-Turbo ```python
import sys

n, m = map(int, input().split())
s = input()

cnt = 0
tmp = 0
for i in range(n):
if s[i] == '0':
tmp = 0
elif s[i] == '1':
tmp += 1
if tmp <= m:
continue
else:
cnt += 1
tmp = 1
else:
tmp += 1
if tmp <= m + cnt:
continue
else:
cnt += 1
tmp = 1

print(cnt)
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
Qwen2-72B-Instruct ```python
N, M = map(int, input().split())
S = input()

# Count the number of days with competitive programming events
num_events = S.count('2')

# Calculate the number of additional T-shirts needed
additional_shirts = max(0, num_events - M)

# Print the answer
print(additional_shirts)
```
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
baichuan4 ```python
# YOUR CODE HERE
import sys

# Read input from stdin
input_data = sys.stdin.read().strip().split()
N, M = map(int, input_data[0].split())
S = input_data[1]

# Count the number of events where a logo T-shirt is needed
logo_shirt_days = S.count('2')

# Calculate the minimum number of logo T-shirts needed
min_logo_shirts_needed = max(0, logo_shirt_days - M)

# Print the result to stdout
print(min_logo_shirts_needed)
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
doubao ```python
N, M = map(int, input().split())
S = input()

logo_needed = 0
shirt_in_use = 0

for c in S:
if c == '1':
shirt_in_use += 1
elif c == '2':
shirt_in_use += 1
logo_needed = max(logo_needed, shirt_in_use - M)

print(logo_needed)
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
N, M = map(int, input().split())
S = input().strip()

K_logo_needed_overall = 0
K1 = 0
K2 = 0

for i in range(N):
if S[i] == '0':
K_logo_needed_in_segment = K2 + max(0, K1 - M)
K_logo_needed_overall = max(K_logo_needed_overall, K_logo_needed_in_segment)
K1 = 0
K2 = 0
else:
if S[i] == '1':
K1 += 1
elif S[i] == '2':
K2 += 1

# Process the last segment if it doesn't end with '0'
K_logo_needed_in_segment = K2 + max(0, K1 - M)
K_logo_needed_overall = max(K_logo_needed_overall, K_logo_needed_in_segment)

print(K_logo_needed_overall)
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
kimi ```python
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
S = input().rstrip()
ans = 0
cnt = 0
for i in range(N):
if S[i] == '0':
cnt = 0
elif S[i] == '1':
cnt += 1
if cnt > M:
ans += 1
cnt = 1
elif cnt < M:
cnt += 1
else:
ans += 1
cnt = 1
print(max(0, ans))
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
minimax ```python
# YOUR CODE HERE
N, M = map(int, input().split())
S = input()

# Initialize variables to track the number of logo T-shirts needed
# and the number of logo T-shirts worn on the last day.
# We need to track the last day because if Takahashi attends a comp event on the last day,
# he can wear a logo T-shirt that he wore on a previous day and washed on the last day.
# This is because he won't need it after the last day.
logo_tshirts_needed = 0
last_day_logo_worn = 0

# Iterate through each day's schedule
for day in S:
if day == '1': # If he goes out for a meal
# He can wear a plain T-shirt or a logo T-shirt.
# If he has no plain T-shirts left, he needs to wear a logo T-shirt.
if M == 0:
logo_tshirts_needed += 1
else:
M -= 1 # Wear a plain T-shirt and put it in the wash
elif day == '2': # If he attends a competitive programming event
# He must wear a logo T-shirt		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
wenxinyiyan ```python
import sys

def min_tshirts_to_buy(N, M, S):
logo_tshirts = 0
plain_tshirts = M
dirty_tshirts = 0
for char in S:
if char == '0':
dirty_tshirts = 0 # Wash all dirty tshirts
elif char == '1':
if plain_tshirts > 0:
plain_tshirts -= 1
dirty_tshirts += 1
else:
logo_tshirts += 1
dirty_tshirts += 1
elif char == '2':
logo_tshirts += 1
dirty_tshirts += 1

# If there are still dirty tshirts at the end, we need to buy enough logo tshirts to cover them
logo_tshirts += max(0, dirty_tshirts - plain_tshirts)

return logo_tshirts

# Read input from stdin
N, M = map(int, input().split())
S = input().strip()

# Calculate and print the minimum number of tshirts to buy
print(min_tshirts_to_buy(N, M, S))
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
zhipu ```python
def main():
import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
M = int(data[1])
S = data[2]

# Initialize variables
plain_tshirts = M
logo_tshirts = 0
additional_logo_needed = 0

# Track the number of consecutive days with events
consecutive_days = 0

for day in S:
if day == '0':
# Wash all T-shirts, reset counters
plain_tshirts = M
logo_tshirts = additional_logo_needed
consecutive_days = 0
elif day == '1':
# Needs either plain or logo T-shirt
if plain_tshirts > 0:
plain_tshirts -= 1
elif logo_tshirts > 0:
logo_tshirts -= 1
else:
additional_logo_needed += 1
consecutive_days += 1
elif day == '2':
# Needs logo T-shirt
if logo_tshirts > 0:
logo_tshirts -= 1
else:
additional_logo_needed += 1
consecutive_days += 1

# Output the minimum number of additional logo T-shirts needed
print(additional_logo_needed)

if __name__ == "__main__":
main()
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]
deepseek-v3 ```python
# YOUR CODE HERE
N, M = map(int, input().split())
S = input().strip()

# Initialize the number of required logo T-shirts
required_logo = 0
current_plain = M
current_logo = 0

for i in range(N):
if S[i] == '0':
# Wash all T-shirts, reset counts
current_plain = M
current_logo = 0
elif S[i] == '1':
# Use plain T-shirt first, if available
if current_plain > 0:
current_plain -= 1
else:
# Use logo T-shirt
if current_logo > 0:
current_logo -= 1
else:
# Need to buy a new logo T-shirt
required_logo += 1
current_logo += 0 # Since it's used immediately
elif S[i] == '2':
# Must use logo T-shirt
if current_logo > 0:
current_logo -= 1
else:
# Need to buy a new logo T-shirt
required_logo += 1
current_logo += 0 # Since it's used immediately

print(required_logo)
```		 [{"input": "6 1\n112022\n", "output": "2\n", "testtype": "stdin"}, {"input": "3 1\n222\n", "output": "3\n", "testtype": "stdin"}, {"input": "2 1\n01\n", "output": "0\n", "testtype": "stdin"}]