{"raw_statement":[{"iden":"problem statement","content":"For a string $T$ consisting of lowercase English letters, consider the question below, and let $f(T)$ be the answer.\n\n> Find the number of different strings obtained by performing the following operation any number of times: delete the first character from $T$ and append it to the end.\n\nYou are given a string $S$ of length $N$ consisting of lowercase English letters. You can perform the operation below at most $K$ times (possibly zero).\n\n*   Choose a character of $S$ and change it to any lowercase English letter.\n\nFind the minimum possible value of $f(S)$ after your operations."},{"iden":"constraints","content":"*   $1 \\le N \\le 2000$\n*   $0 \\le K \\le N$\n*   $S$ is a string of length $N$ consisting of lowercase English letters.\n*   $N$ and $K$ are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$S$"},{"iden":"sample input 1","content":"4 1\nabac"},{"iden":"sample output 1","content":"2\n\nIf you change the fourth character `c` to `b` in the first operation, you get $S=$ `abab`, with $f(S)=2$.\n$f(S)$ cannot be made $1$ or less in one or fewer operations, so the answer is $2$."},{"iden":"sample input 2","content":"10 0\naaaaaaaaaa"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"6 1\nabcaba"},{"iden":"sample output 3","content":"3"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}