30090번 - 백신 개발 서브태스크

문제

평소 정보 보안에 관심이 많은 진흥이는 최근 들어 유행하고 있는 컴퓨터 바이러스에 대한 백신을 개발하려고 한다. 바이러스는 $N$개의 문자열로 이루어져 있다고 한다. 진흥이가 열심히 연구한 결과, 이 바이러스를 처치할 방법은 다음과 같다.

• 바이러스를 구성하는 $N$개의 문자열을 적당한 순서를 정하여 하나로 이어 붙여야 한다.
• 앞에 붙는 문자열의 마지막 $k$글자와 뒤에 붙는 문자열의 첫 $k$글자가 일치하도록 하는 1ドル$이상의 정수 $k$가 존재해야 한다. 조건을 만족하는 가장 큰 $k$에 대해서, 앞에 붙는 문자열의 마지막 $k$글자를 삭제하고, 뒤에 붙는 문자열을 그대로 붙인다.
• $N$개의 문자열을 모두 이어 붙였을 때 가장 짧은 문자열이 백신이 된다.

진흥이를 도와 백신이 되는 문자열의 길이를 출력하자. 반드시 답이 존재하는 경우만 주어진다.

입력

첫 번째 줄에 바이러스를 구성하고 있는 문자열의 수 $N$ (1ドル \le N \le 9$)이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐서 바이러스를 구성하는 문자열이 주어진다. 이 때 문자열의 길이는 10ドル$이하이며, 영어 대문자로만 구성되어 있다.

출력

백신이 되는 문자열의 길이를 출력한다.

제한

서브태스크

힌트