{"raw_statement":[{"iden":"problem statement","content":"AtCoder Inc. sells [T-shirts with its logo](https://suzuri.jp/AtCoder/5510290/t-shirt/s/ash).\nYou are given Takahashi's schedule for $N$ days as a string $S$ of length $N$ consisting of `0`, `1`, and `2`.  \nSpecifically, for an integer $i$ satisfying $1\\leq i\\leq N$,\n\n*   if the $i$\\-th character of $S$ is `0`, he has no plan scheduled for the $i$\\-th day;\n*   if the $i$\\-th character of $S$ is `1`, he plans to go out for a meal on the $i$\\-th day;\n*   if the $i$\\-th character of $S$ is `2`, he plans to attend a competitive programming event on the $i$\\-th day.\n\nTakahashi has $M$ plain T-shirts, all washed and ready to wear just before the first day.  \nIn addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.\n\n*   On days he goes out for a meal, he will wear a plain or logo T-shirt.\n*   On days he attends a competitive programming event, he will wear a logo T-shirt.\n*   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.\n*   Once he wears a T-shirt, he cannot wear it again until he washes it.\n\nDetermine 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$.  \nAssume that the purchased T-shirts are also washed and ready to use just before the first day."},{"iden":"constraints","content":"*   $1\\leq M\\leq N\\leq 1000$\n*   $S$ is a string of length $N$ consisting of `0`, `1`, and `2`.\n*   $N$ and $M$ are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$S$"},{"iden":"sample input 1","content":"6 1\n112022"},{"iden":"sample output 1","content":"2\n\nIf Takahashi buys two logo T-shirts, he can wear T-shirts as follows:\n\n*   On the first day, he wears a logo T-shirt to go out for a meal.\n*   On the second day, he wears a plain T-shirt to go out for a meal.\n*   On the third day, he wears a logo T-shirt to attend a competitive programming event.\n*   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.\n*   On the fifth day, he wears a logo T-shirt to attend a competitive programming event.\n*   On the sixth day, he wears a logo T-shirt to attend a competitive programming event.\n\nIf he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print $2$."},{"iden":"sample input 2","content":"3 1\n222"},{"iden":"sample output 2","content":"3"},{"iden":"sample input 3","content":"2 1\n01"},{"iden":"sample output 3","content":"0\n\nHe does not need to buy new T-shirts."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}