|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||2||0||0||0.000%|
Every sequence of small letters a and b (also the empty sequence) is called an ab-word. If X = [x1, ..., xn] is an ab-word and i, j are integers such that 1 ≤ i ≤ j ≤ n then X[i..j] denotes the subword of X consisting of the letters xi, ..., xj. We say that an ab-word X = [x1, ..., xn] is nice if it has as many letters a as b and for all i = 1, ..., n the subword X[1,i] has at least as many letters a as b.
Now, we give the inductive definition of the similarity between nice ab-words:
A level of diversity of a non-empty set S of nice ab-words is the maximal number of ab-words that can be chosen from S in such a way that for each pair w1, w2 of chosen words, w1 is not similar to w2.
Write a program that:
In the first line of the standard input there is a number n of elements of the set S, 1 ≤ n ≤ 1,000; in the following n lines there are elements of the set S, i.e. nice ab-words (one word in each line); the first letter of every ab-word is the first symbol in line and there are no spaces between two consecutive letters in the word; the length of every ab-word is an integer from the range [1..200].
In the first and only line of the standard output there should be written one integer — the level of diversity of S.
3 aabaabbbab abababaabb abaaabbabb