GSHS에서 지식재산일반을 가르치는 코빡이(코다리마빡이)는 학생들이 직접 특허를 출원해 보며 특허 등록 과정과 절차를 익히는 활동을 준비했다. 모든 수행평가를 이 활동 하나로 대체하려는 속셈은 결코 없다.
특허를 출원하려면 학생 본인의 도장이 필요하다. 도장이 없는 학생들을 위해 친절한 코빡이는 모든 알파벳 조각이 들어 있는 조립식 도장을 가져왔다. 하지만 수업 시간이 짧아서, 최대한 적은 횟수의 연산으로 모든 학생의 이름을 찍어야 한다.
학생은 명이고, 번째 학생의 이름은 문자열 이다.
조립식 도장에는 조각이 왼쪽부터 한 줄로 끼워지며, 최대 개까지 끼울 수 있다. 도장은 처음에 비어 있고, 다음 세 가지 연산을 할 수 있다. 연산 하나를 할 때마다 연산 횟수가 늘어난다.
이미 끼워진 조각들의 순서를 바꾸는 방법은 없다. 예를 들어 도장에 ABC가 끼워져 있을 때 BCA를 만들려면, A를 빼고 맨 뒤에 A를 채우면 된다.
각 학생의 이름은 찍기를 정확히 한 번 해서 찍어야 하고, 찍는 순간 도장의 조각들을 왼쪽부터 읽은 문자열이 그 학생의 이름과 같아야 한다. 이름을 찍는 순서는 자유롭게 정할 수 있다.
모든 학생의 이름을 한 번씩 찍기 위해 필요한 연산 횟수의 최솟값을 구한다.
첫 번째 줄에 양의 정수 이 주어진다.
두 번째 줄부터 개의 줄 중 번째 줄에 문자열 가 주어진다.
첫 번째 줄에 모든 학생의 이름을 한 번씩 찍기 위해 필요한 연산 횟수의 최솟값을 출력한다.
