미래 세대

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

요약

주어진 이름에서 각각 부분 수열을 골라 문자열이 사전순으로 증가하게 만들 때 길이의 합의 최댓값을 구합니다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 비트 연산, 문자열, 그리디
정답자: 아직 제출이 없습니다

문제

Andi는 결혼을 앞두고 있다. Andi와 배우자는 N명의 자녀를 가질 계획이다. 나중에 번거로운 일을 피하기 위해 Andi는 모든 자녀의 이름을 미리 정하려고 한다. 구체적으로, 각 자녀의 이름은 자신보다 나이가 많은 형제자매의 이름보다 사전순으로 커야 한다. 물론 배우자도 이 생각에 동의한다. 문자열 A가 문자열 B보다 사전순으로 크다는 것은, B가 A의 접두사이거나, Aj = Bj인 모든 j < i에 대해 Ai > Bi인 인덱스 i가 존재한다는 뜻이다. 이름은 한 글자만큼 짧아도 되지만 빈 문자열일 수는 없다.

Andi는 행복하게 지내던 어느 날, 장래 시할머니(배우자의 할머니)에게 이 결혼 계획을 이야기했다. Andi가 손녀와 N명의 자녀를 가질 계획이라는 말을 들은 할머니는 이름 N개를 주면서, i번째 이름은 i번째 자녀에게만 쓸 수 있다고 했다.

할머니와 긴 논의 끝에 Andi는 다음과 같이 합의했다. i번째 자녀의 이름은 할머니가 준 i번째 이름의 부분 수열이어야 한다. 문자열 A가 문자열 B의 부분 수열이라는 것은, B에서 0개 이상의 문자를 지우고 남은 문자의 순서를 바꾸지 않아 A를 얻을 수 있다는 뜻이다. 예를 들어 ABC는 DAEBCCB의 부분 수열이지만, EFG는 FABEGC의 부분 수열이 아니다.

Andi는 할머니가 준 이름 목록이 마음에 들지 않지만, 할머니의 바람과 자신의 바람(각 자녀의 이름이 형제자매의 이름보다 사전순으로 큰 것)을 모두 만족시킬 수 있음을 보여 배우자의 마음을 사로잡고 싶어 한다. Andi는 자녀 이름들의 총 길이로 가능한 최댓값이 얼마인지 궁금해한다.

예를 들어 N = 3이고 할머니가 준 이름이 (KARIM, PARBUDI, CHANDRA)라 하자. Andi의 바람을 만족하는 이름 조합의 예는 다음과 같다.

[AR, BI, CRA], 총 길이 2 + 2 + 3 = 7.
[ARI, BUDI, CHANDRA], 총 길이 3 + 4 + 7 = 14.
[ARIM, ARUDI, CHANDRA], 총 길이 4 + 5 + 7 = 16.
[AIM, ARBUDI, CHANDRA], 총 길이 3 + 6 + 7 = 16.
...

이 예에서 Andi의 바람을 만족하는 모든 이름 조합 가운데 최대 총 길이는 16이다. 유효한 이름 조합을 만들 수 없는 경우에는 -1을 출력해야 한다.

예를 들어 N = 2이고 할머니가 준 이름이 (ZORO, ANDI)라 하자. 이 예에서 2번째 이름의 모든 부분 수열은 1번째 이름의 모든 부분 수열보다 사전순으로 작으므로, 유효한 이름 조합을 만들 수 없다.

입력

입력은 자녀 수를 나타내는 정수 N (1 ≤ N ≤ 15)이 있는 줄로 시작한다. 다음 N개 줄에는 각각 Andi의 장래 시할머니가 준 i번째 이름을 나타내는 문자열 Si (1 ≤ |Si| ≤ 15)가 주어진다. Si는 대문자 알파벳으로만 이루어진다 (Sij ∈ {A - Z}).

출력

자녀 이름들의 총 길이로 가능한 최댓값을 한 줄에 출력한다. 유효한 이름 조합을 만들 수 없으면 -1을 출력한다.

예제3

예제 1
입력
```
3
KARIM
PARBUDI
CHANDRA
```
예상 출력
```
16
```
예제 2
입력
```
2
ZORO
ANDI
```
예상 출력
```
-1
```

예제 3

입력

7
HAVE
FUN
IN
ICPC
JAKARTA
TWENTY
EIGHTEEN

예상 출력