이상한 편집기

브루는 지금 매우 비효율적인 편집기로 글을 쓰고 있다. 브루는 이 편집기로 원하는 글을 쓰려고 한다.

편집기에는 임시 저장 공간인 스택이 마련되어 있다. 편집기는 이 스택을 이용해 글을 쓴다. 편집기가 지원하는 연산은 다음 세 가지뿐이다.

1. 스택 뒤에 문자 하나를 추가한다.
2. 스택 맨 뒤의 문자를 하나 제거한다. 스택이 비어 있을 때는 아무 것도 하지 않는다.
3. 스택에 저장된 문자열을 글에 붙여 넣는다. 이때 스택은 그대로 유지된다.

브루를 위해 원하는 글을 쓰는 데 필요한 연산의 최소 횟수를 계산하자. 글을 모두 쓴 뒤에는 스택이 비어 있지 않아도 된다.

첫째 줄에 브루가 편집기로 쓰고 싶은 글 S가 주어진다. (1 ≤ |S| ≤ 2000)

S는 알파벳 소문자로만 이루어져 있다.

브루가 글을 쓰기 위해 해야 하는 연산의 최소 횟수를 출력한다.