이니셜

면접 대비

시간 제한3초메모리 제한512 MB

요약

각 학생의 디렉터리 이름은 성 머리글자와 이름 머리글자로 시작한다. 전체 이름에서 글자를 덧붙여 학급 순서대로 이름이 엄격히 증가하도록 만들 때, 추가하는 글자 수의 최솟값을 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 문자열, 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

채점자는 수업 명단 순서대로 과제를 채점한다. 명단은 학생의 성 뒤에 이름을 붙이고(Harry Potter는 PotterHarry가 된다) 모든 글자를 소문자로 바꾼 다음, 그 문자열을 사전순으로 정렬해 만든다.

학생마다 유닉스 디렉터리가 하나씩 필요하다. 채점자는 게을러서 디렉터리 이름을 이니셜로만 짓는다. 이니셜은 성의 첫 글자 뒤에 이름의 첫 글자를 붙인 것이다. Harry Potter의 이니셜은 PH다. 그러자 문제가 두 가지 한꺼번에 생겼다. 시스템이 디렉터리를 나열하는 순서가 명단 순서와 어긋나고, 이름이 겹치는 디렉터리도 생긴다.

이를 바로잡으려고 채점자는 디렉터리 이름 뒤에 글자를 더 붙인다. 붙일 글자는 마음대로 고르지 못한다. $k$ 글자를 더 붙인 이름은 성의 앞 $k+1$ 글자 뒤에 이름의 첫 글자를 붙인 것이고, 성을 다 쓰고 나면 남은 글자는 이름의 두 번째 글자부터 이어서 가져온다. Harry Potter는 0글자를 붙이면 PH, 2글자면 PotH, 5글자면 PotterH, 6글자면 PotterHa가 된다. 성의 길이가 $p$ , 이름의 길이가 $q$ 인 학생은 최대 $p + q - 2$ 글자까지 붙일 수 있고, 그러면 성과 이름을 모두 쓴 것이 된다.

시스템은 디렉터리 이름을 한 글자씩 비교하며 대소문자를 구분하지 않는다. 그래서 Hab과 HAB은 같고, Ha는 Hat보다 앞선다. 채점자는 명단 순서대로 읽은 디렉터리 이름이 이 비교에서 엄격하게 증가하기를 원한다. 엄격하게 증가하면 이름이 겹치는 디렉터리도 없다.

더 붙이는 글자 수의 합을 최소로 하라.

학생이 Bob Harris, Andrea Hat, Zanny Zan 세 명이라고 하자. 명단 순서는 Bob Harris, Andrea Hat, Zanny Zan이지만 이니셜 HB, HA, ZZ는 순서가 맞지 않는다. Bob Harris에 한 글자, Andrea Hat에 두 글자를 붙이면 HaB, HatA, ZZ가 되어 순서가 맞고, 세 글자가 최소다.

입력

첫째 줄에 학생 수 $N$ 이 주어진다 ( $2 \le N \le 1000$ ). 다음 $N$ 개 줄에는 학생 한 명의 이름과 성이 공백 하나로 구분되어 주어진다. 이름과 성은 영어 대문자와 소문자로만 이루어지고, 각각 한 글자 이상이다. 한 학생의 이름과 성을 합친 길이는 80글자 이하다. 위에서 정의한 대로 성과 이름을 붙인 문자열이 서로 같은 학생은 없다.

출력

더 붙여야 하는 글자 수의 합의 최솟값을 출력한다.

예제3

예제 1
입력
```
3
Bob Harris
Andrea Hat
Zanny Zan
```
예상 출력
```
3
```
예제 2
입력
```
3
Bob Ab
Al Ac
Cy Ad
```
예상 출력
```
2
```
예제 3
입력
```
2
A Lin
B Li
```
예상 출력
```
1
```