You are given a string $S$ that contains lowercase English letters. In one step, you can choose an index $i$ from $S$ and assign the next letter in the alphabet ($'a' \rightarrow 'b', 'b' \rightarrow 'c', \dots, 'z' \rightarrow 'a'$) to $S_i$. Define $f(str)$ as the number of indices $i \ (1 \le i < |str|)$ where $str_i \neq str_{i + 1}$.

You are given a number $K$. Now, your task is to determine the minimum number of steps required to perform on the string $S$ to obtain a string $S'$ such that $f(S') \le K$.

Input format

• First line: String $S$ $(1 \le |S| \le 2048)$
• Second line: Integer $K$ $(0 \le K < \min(|S|,32))$

Output format

Print the minimum number of steps.