Hide

Problem K
Christian's Piano

Languages en sv

Christian wants to learn to play the piano but can only manage to play with his index finger right now. Currently, he is practicing hard to learn a piece. A piece is described by a sequence of keys to be pressed in order. For example, the piece abdaa indicates that he should press the keys a, b, d, a, a in order.

However, you notice that he struggles to move his finger quickly between the keys. Curiously, it always takes him exactly one second to move his finger one key to the side but zero seconds to press a key.

To help him, you plan to rearrange the order of the piano keys so that the total time it takes to play the piece is minimized.

For example, if the piece he is trying to learn is abdaa and the piano has the order abd $\cdots $ (the rest of the piano is not shown as it does not affect the answer), it will take a total of $4$ seconds to play the piece. The distances when he plays the piece are as follows:

  • a to b takes one second.

  • b to d takes one second.

  • d to a takes two seconds.

  • a to a takes zero seconds.

This means that it takes a total of four seconds to play the piece abdaa on a piano with the order abd $\cdots $.

Write a program that reads a piece and outputs the total time it takes for Christian to play the piece on the piano with the best possible key order.

Input

The first and only line of input contains a string $S$ ($1 \leq |S| \leq 200$), the piece that Christian wants to learn. The piece consists of characters from a-z and contains at most $15$ distinct characters.

Output

Print an integer: the number of seconds it takes for Christian to play the piece on a piano with the best possible key order.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

Group

Point value

Constraints

$1$

$20$

The piece contains at most $8$ distinct characters.

$2$

$80$

No additional constraints.

Explanation of sample 2

One possible optimal order of the piano keys is adbc.

Sample Input 1 Sample Output 1
abdaa
4
Sample Input 2 Sample Output 2
abdaadbc
7