Module: 동적 프로그래밍의 패턴

Problem

클로이는 친구에게 편지를 쓰고 싶어합니다. 문자 - 라틴 소문자로 구성된 문자열 s.
불행하게도 Chloe는 편지를 쓰기 시작하자마자 편지가 너무 길고 전체를 쓰려면 시간이 매우 오래 걸린다는 것을 깨달았습니다. 그래서 그녀는 문자열 자체 대신 문자열 s의 압축된 버전을 작성하려고 합니다.

문자열 s — 문자열 c₁, s₁, c₂, s₂, ..., c_k, s_k, 여기서 c_i — a_i(선행 0 없음) 및 s_i — 소문자 라틴 문자의 일부 문자열입니다. Chloe가 문자열 s₁을 정확히 ₁번 쓰면 s₂는 정확히 ₂번입니다. on , 문자열 s를 생성합니다.
압축된 버전의 길이는 |c₁| + |s₁| + |c₂|  +  |s₂|... |c_k| + |s_k|. 모든 압축 버전 중에서 Chloe는 길이가 가장 짧은 버전을 선택하려고 합니다. 클로이가 가장 짧은 길이를 찾도록 도와주세요.

입력:
입력의 한 줄에는 소문자 라틴 문자(1 ≤ |s| ≤ 5000)로 구성된 문자열 s가 포함됩니다.

출력:
단일 정수 인쇄 — 문자열 s의 압축된 버전의 최소 길이.

예:
  <몸>

설명:
첫 번째 예에서 Chloe는 다음 버전을 선택합니다. c₁ — 10, s₁ — 가.
두 번째 예에서 Chloe는 다음 버전을 선택합니다. c₁ — 1, s₁ — 알파벳.
세 번째 예에서 Chloe는 다음 버전을 선택합니다. c₁ — 2, s₁ — c, c₂ — 1, s₂ — z, c₃ — 4, s₃ — 약.
 

입력	출력
아아아아아아아아아아아아아아아	3
abcab	6
cczabababab	7