시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 132 119 112 89.600%

문제

천하제일코딩대회를 마치고 $N$명의 운영진은 회전 초밥집으로 회식을 가서 스시를 먹기로 했다. 이 식당에는 총 26가지의 스시가 있으며, 이는 문자 A부터 Z까지에 대응하여 생각할 수 있다.

회전 초밥집은 아래 그림과 같이 $N+1$개의 의자와 $N+1$개의 접시로 이루어져 있다. 사람들은 계속 자신의 자리에 앉아 있으며, 매 분마다 접시들은 시계방향으로 한 칸씩 이동한다.

$S_0$에는 셰프가 앉아 있으며, 매 분마다 셰프는 자신 앞에 온 접시가 비어있지 않으면 아무 행동도 하지 않고, 자신 앞에 온 접시가 비어있으면, 한 점의 스시를 만들어 접시에 올린다. 하지만, 현재 상태에서 셰프가 더 이상 스시를 만들지 않아도 모든 손님이 유한한 시간안에 식사를 마칠 수 있음이 보장된다면, 셰프는 더 이상의 스시를 만들지 않는다.

$N$명의 대회 운영진은 각각 $S_1, S_2, \cdots,  S_N$의 자리 중 한 곳에 앉았고, 그들 외의 손님은 없다고 가정한다. $N$명의 대회 운영진 각각은 자신이 오늘 먹고 싶은 스시의 목록이 있고, 목록에 있는 순서대로 먹고자 한다.

매 분마다 각 손님(대회 운영진)은 다음과 같이 행동한다:

  • 자신의 앞에 온 접시에 이번 순서에 먹을 스시가 있으면 먹는다.
  • 아니면, 접시에 손대지 않는다.

초기에 모든 접시는 비어있고, 손님들이 식사를 시작하는(모두 자리에 앉은) 시점부터 셰프는 음식을 만든다고 가정한다.

모든 손님들이 유한한 시간 안에 식사를 마치기 위해 셰프가 만들어야 하는 스시의 최소 개수를 구하여라.

입력

입력의 첫 줄에 $N$이 주어진다.

이후 $i (1 \le i \le N)$번째 줄에는 손님 $i$가 먹고 싶어하는 스시의 목록을 나타내는 문자열 $B_i$가 주어진다.

한 종류의 스시가 한 손님의 목록에 두 번 이상 속할 수 있음에 유의하라.

출력

문제의 답을 나타내는 정수 하나를 출력한다.

제한

  • $1 \le N \le 100$
  • $1 \le len(B_i) \le 100$

예제 입력 1

2
ABCDE
FGH

예제 출력 1

8

예제 입력 2

1
ABCDE

예제 출력 2

5