题目描述

You want to compress a given text passage using backreferences. A backreference is a pair of numbers $[a, b]$ indicating that the next $b$ characters of the string are the same as the $b$ characters starting $a$ characters back from the current position. The two strings may overlap, i.e., $a$ may be smaller than $b$.

Each backreference costs three bytes to encode, regardless of the number of characters represented by the backreference. String characters cost one byte each to encode.

For instance, the string

has 12 characters. But the last nine can be represented as a backreference to the first nine, as follows:

The total cost of this encoded string is 6: 3 bytes for the string abc, and 3 bytes for the backreference.

Output the minimum cost to encode the text passage.

输入格式

The single line of input contains a string $s$, with $1 \le |s| \le 10^5$. This line of text consists of uppercase letters ('A'–'Z'), lower-case letters ('a'–'z'), and spaces. There will not be any spaces at the beginning or end of the line, and no space character will be adjacent to another space character.

输出格式

Output a single integer, which is the minimum cost to represent the input string using backreferences.

abcabcabcabc

6

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

4

A man a plan a canal Panama

25