Repetition

Interview

Time limit1sMemory limit256 MB

Summary

Given a lowercase string S, find the smallest K such that S is a subsequence of the alphabet repeated K times.

Level: Medium4 of 10
Topics: Greedy, String, Implementation
Solved: No attempts yet

Problem

muse wants to post something on a Naver cafe. But the keyboard is broken, so pressing any key types abcdefghijklmnopqrstuvwxyz.

muse still wants to post, but to write the desired text, muse has to do the following.

Type abcdefghijklmnopqrstuvwxyz repeated $K$ times.
Delete unwanted characters with the mouse to finish the final text.

muse finds deleting many characters annoying, so muse wants to minimize $K$ . Given the text muse wants to type, find how many times abcdefghijklmnopqrstuvwxyz must be typed.

Input

The text $S$ that muse wants to type is given. It consists only of lowercase English letters, and its length is $L$ . ( $1 \le L \le 10^5$ )

Output

Print the minimum value of $K$ .

Examples1

Example 1
Input
```
polymath
```
Expected output
```
6
```