Dot Matrix Printer

Time limit1sMemory limit128 MB

Summary

Given a string, find the minimum number of SET/NEXT/WRITE printer commands needed to output it, where NEXT temporarily overrides the next WRITE.

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

Problem

Jongsu bought a dot matrix printer for an Arduino project. After a long implementation effort, he can now send three commands from the Arduino to the printer.

SET(X): stores the character X in the printer's main memory.
NEXT(X): stores the character X in the printer's auxiliary memory.
WRITE: prints the character stored in main memory. However, if the immediately previous command was NEXT, it prints the character stored in auxiliary memory instead.

For example, to print AABAA, the following 8 commands can be used.

SET(A), WRITE, WRITE, SET(B), WRITE, SET(A), WRITE, WRITE

Using NEXT, the same word can be printed with the following 7 commands.

SET(A), WRITE, WRITE, NEXT(B), WRITE, WRITE, WRITE

Given a word consisting only of uppercase English letters, compute the minimum number of commands needed to print the word.

The first command must be SET.

Input

The first line contains the word to print. The word consists only of uppercase English letters, and its length does not exceed 10,000.

Output

Print the minimum number of commands needed to print the given word.

Examples3

Example 1
Input
```
NN
```
Expected output
```
3
```
Example 2
Input
```
IOIX
```
Expected output
```
7
```
Example 3
Input
```
BABCBACA
```
Expected output
```
13
```