String Expansion Operations

You are given a string S and an integer L. In one operation, you can choose a character c which appears in S exactly x times, and then append exactly x copies of c to the end of S. The goal is to perform a sequence of operations so that the length of S is at least L.

Note: If the length of S is already greater than or equal to L, no operations are needed.

Your task is to determine the minimum number of operations required to reach a string length of at least L.

The effect of an operation, if you choose a character that currently appears x times, is that the string's total length increases by x. Moreover, the frequency of that particular character in S doubles after the operation. It is optimal to always choose the character with the highest frequency.

If we let n be the initial length of S and M be the maximum occurrence count of any character in S, then after k operations (always choosing the character with current maximum frequency), the string length becomes:

[ n + M \times (2^k - 1) \ge L ]

Solve for the minimum k satisfying the inequality above.

inputFormat

The input consists of two lines:

• The first line contains a non-empty string S consisting of lowercase English letters.
• The second line contains a positive integer L, representing the target minimum length of S.

outputFormat

Output a single integer, which is the minimum number of operations required so that the length of S becomes greater than or equal to L.

sample

a
6

3