Strange Keyboard

Interview

Time limit2sMemory limit128 MB

Summary

Given a string on a cursor-based keyboard, find the minimum Left/Right/Enter presses needed to print every character in alphabetical order.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Sorting, String
Solved: No attempts yet

Problem

Donghyeok's keyboard has three buttons, Left, Right, and Enter, and one LCD window. The string S is shown in the LCD window, and initially the cursor is on the leftmost character of S.

Left and Right move the cursor one position in that direction only when the cursor can remain inside the LCD window. The window length is exactly |S|, so the cursor never leaves the window. Pressing Enter sends the character under the cursor to the computer screen, and that position becomes blank.

Donghyeok wants to print every character of S on the computer screen in alphabetical order. Every occurrence must be printed: if S contains three a characters, the screen must receive three a characters.

Given the string in the LCD window, compute the minimum number of button presses needed to print all characters in alphabetical order.

Input

The first line contains the string S shown in the LCD window. The length of S is at most 50, and S consists only of lowercase English letters.

Output

Print the minimum number of button presses needed to print the characters of S in alphabetical order.

Hint

For aaa, one optimal sequence is Enter -> Right -> Enter -> Right -> Enter, for a total of 5 presses.

Examples4

Example 1
Input
```
aaa
```
Expected output
```
5
```
Example 2
Input
```
ba
```
Expected output
```
4
```
Example 3
Input
```
abba
```
Expected output
```
9
```
Example 4
Input
```
acbbc
```
Expected output
```
12
```