18799번 - 이상한 편집기

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

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

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

브루를 위해, 원하는 글을 쓰기 위한 연산의 최소 횟수를 계산해 보자. 글을 모두 쓴 뒤, 스택의 상태는 비어 있지 않아도 된다.

브루가 편집기를 이용해 쓰고 싶은 글 S가 주어진다. (1 ≤ |S| ≤ 2000)

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

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