빠른 타이핑

키보드, Pixabay의 DomAlberts 촬영

경쟁 프로그래밍에서는 키보드로 빠르게 입력할 수 있으면 유용하다. Bjarki는 분당 더 많은 단어를 입력할 수 있도록 TypeRacer에서 자주 연습한다. 가끔 Bjarki는 단어를 입력하기 시작한 뒤, 자신이 생각하고 있는 단어를 완성하기 위해 TAB 키를 누를 수 있으면 좋겠다고 생각한다. 그러면 많은 시간을 절약할 수 있지만, 가능한 단어가 단 하나뿐인 경우에만 가능하다.

따라서 Bjarki는 자신이 입력하려는 글에 등장하는 모든 단어가 포함된 사전을 컴퓨터에 설정한다. 예를 들어 Bjarki가 입력하는 글이 ANNA OG AMMA ETA MAT SAMAN일 수 있으며, 이를 입력하려면 Bjarki는 $26$개의 키를 눌러야 한다. 사전을 사용하여 AN! O! AM! E! M! S! 키를 누른다면, 여기서 !은 Bjarki가 TAB 키를 눌렀음을 나타내며, 그는 $19$개의 키를 누르게 되므로 $7$번의 키 입력을 절약한다. 이 시점에는 그가 ANNA을 입력하려는지 AMMA을 입력하려는지 확실하지 않으므로, A 직후에는 TAB 키를 사용할 수 없음에 유의하라. 또한 사전에 단어가 단 하나뿐이라면 Bjarki는 곧바로 TAB 키를 누를 수 있다. 아직 어떤 문자도 입력하지 않았더라도 가능한 단어가 단 하나뿐이기 때문이다.

Bjarki가 입력하는 글이 주어질 때, 그는 키보드 입력을 몇 번 절약할 수 있는가?

채점

그룹 | 점수 | 제한

1 | 30 | $1 \leq n \leq 10$이고 각 단어는 최대 $10$개의 문자로 이루어진다

2 | 40 | 각 단어는 최대 $10$개의 문자로 이루어진다

3 | 30 | 추가 제한 없음

첫째 줄에는 Bjarki가 글에 입력하는 단어의 수를 나타내는 정수 $1 \leq n \leq 5 \cdot 10^5$ 하나가 주어진다. 다음 줄에는 Bjarki가 입력하는 글이 주어진다. 글은 공백으로 구분된 하나 이상의 단어로 이루어지며, 문자의 수는 최대 $10^6$개이다. 단어에는 영어 알파벳 대문자만 포함된다.

Bjarki가 절약하는 키보드 입력 횟수를 한 줄에 출력한다.