P6101 [EER2] Rude Speech

You are being rude!!

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.

The first line contains a string $S$. The second line contains a positive integer $L$. Their meanings are as described in the statement.

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

### 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