시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB21150.000%

문제

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

서브태스크

번호배점제한
147

1 ≤ li, N ≤ 50

215

1 ≤ li, N ≤ 200

338

None

예제 입력 1

5
8 BALANDIS
5 PALIS
6 SPALIS
4 PLIS
3 LIS

예제 출력 1

3

예제 입력 2

4
6 ADOMAS
4 ADAS
8 VYTAUTAS
5 VYTAS

예제 출력 2

0

채점 및 기타 정보

  • 예제는 채점하지 않는다.