훈이는 학생들의 ID가 앞으로 읽어도 뒤로 읽어도 똑같다면 재밌을 거라는 생각을 했다.

그래서 서버에 등록된 학생들의 ID들을 전부 팰린드롬(팰린드롬(회문) : 거꾸로 읽어도 똑같은 문장,단어를 말한다.)으로 만들어 버리기로 했다.

ID는 26개 이하의 알파벳 소문자로만 이루어져 있고, 그 길이는 M (1≤M≤2,000)이다.

abcb와 같은 ID는 뒤에 a를 추가해서 abcba로 만들 수도 있고, 앞에 bcb를 추가해서 bcbabcb와 같이 만들 수도 있다.

또한, a를 삭제해서 bcb로 만들 수도 있다. 특이하게도, 정올 서버에서 학생들의 ID를 고칠 때 추가하거나 삭제하는 문자에 따라 걸리는 시간이 다르다.

각 글자를 추가하거나 삭제할 때 드는 시간(0 이상 10,000 이하)이 주어지면, 학생의 ID를 팰린드롬으로 만들기 위해 걸리는 시간의 최소값을 구하자.

단, 빈 문자열 또한 팰린드롬으로 간주한다(앞으로 읽어도 뒤로 읽어도 아무튼 똑같기 때문에).

팰린드롬 timer 1초 memory 128MB

팰린드롬 1초 128MB