농부 창호는 소를 가지고 있는데, 이 소들은 ID들을 가지고 있다. 이 ID들은 M의 길이를 가지며(1≤M≤2,000) N개의(1≤N≤26) 서로 다른 소문자로 구성되어 있다.

우리는 이 ID를 편집해서 앞에서부터 읽으나 뒤에서부터 읽으나 같은(회문) ID로 보이도록 만들고자 한다.

ID의 어떠한 위치에라도 소문자들을 추가할 수도 있고 제거할 수도 있는데, 각각 소문자별로 추가하거나 삭제하는데 드는 비용이 모두 다르다.

우리는 이 비용을 최소화하면서 회문을 만들 때 최소 비용이 얼마인지 알려주는 프로그램을 작성하라.

ID 만들기 timer 1초 memory 128MB

ID 만들기 1초 128MB