Description

Keai wants to participate in an open contest, but she gets rejected every time.

Keai is very angry, so she learned to speak rudely.

Keai uses a string $S$ to store what she wants to say, but this sentence is too mild. To speak rudely, Keai needs to operate on the string. In each operation, Keai can choose a character $c$. If $c$ appears $x$ times in string $S$, then Keai will append $x$ copies of character $c$ to the end of $S$.

Keai thinks that only when the length of this string is at least $L$ can she speak rudely. Keai wants to know the minimum number of operations needed to make the length of this string greater than or equal to $L$.

If you do not tell Keai, Keai will speak rudely to you.

Input Format

The first line contains a string $S$.

The second line contains a positive integer $L$.

Their meanings are as described in the statement.

Output Format

Output one integer in a single line, representing the minimum number of operations.

nzhtl1477
15

2

Hint

Sample Explanation

In the first operation, choose character 7. The string becomes nzhtl147777, and the length is $11$.

In the second operation, choose character 7. The string becomes nzhtl1477777777, and the length is $15$.

Constraints and Notes

For $100\%$ of the testdata, $1\leq |S|\leq 10^6$, $1\leq L\lt 2^{64}$. The string $S$ contains only uppercase letters, lowercase letters, and digits, for a total of $62$ different characters.

$|S|$ denotes the length of string $S$.

This problem has $4$ subtasks, each with the following constraints:

Subtask 1 ($15$ points): It is guaranteed that $|S|=L-1$.

Subtask 2 ($20$ points): It is guaranteed that only character d appears in $S$.

Subtask 3 ($30$ points): $L\leq 10^6$.

Subtask 4 ($35$ points): No special constraints.

Notes

Please pay attention to the upper bound of $L$.

The data is generated on Windows. Note that the line ending of each line is \r\n rather than \n.

Translated by ChatGPT 5