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.