You have a keyboard with keys. Initially, key () is mapped to the -th lowercase English letter, i.e., key to ‘a’, key to ‘b’, ..., and key to ‘y’. You also have an empty string .
You can perform the following two operations any number of times, in any order:
Choose an integer () and a lowercase English letter , and change the mapping of key to . This operation costs .
Choose an integer (), and append the letter currently mapped to key to the end of . This operation costs .
You are given a string consisting of lowercase English letters. Find the minimum total cost required to make equal to .
输入格式
The input consists of a single test case in the following format.
The only line contains a string consisting of lowercase English letters. The length of is between and , inclusive.
