Mysterious words

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

요약

한 글자씩 지워 사전에 있는 단어로 계속 이어지는 삭제 사슬이 가장 긴 단어의 길이를 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 해시맵, 문자열
정답자: 아직 제출이 없습니다

문제

Vincent likes mysterious words. Mystery level is defined by the number of letters that can be removed from a word one by one such that the new word exists in the dictionary.

For example, if the dictionary contains words BALANDIS, PALIS, SPALIS, PLIS, LIS, word SPALIS has a mystery level of 3: SPALIS → PALIS → PLIS → LIS. Word BALANDIS has a mystery level 0, since removing letters from it doesn’t produce any words in the dictionary.

Help Vincent find the most mysterious word in the given dictionary.

입력

The first line contains an integer N – the number of words in a dictionary. The following N lines consist of a number li, followed by a single space and a word of length li. All words in the dictionary are different and contain only uppercase English letters (A – Z).

출력

Output a single integer – the mystery level of the most mysterious word in the dictionary.

제한

1 ≤ li, N ≤ 2000

예제2

예제 1

입력

5
8 BALANDIS
5 PALIS
6 SPALIS
4 PLIS
3 LIS

예상 출력

예제 2
입력
```
4
6 ADOMAS
4 ADAS
8 VYTAUTAS
5 VYTAS
```
예상 출력
```
0
```