Familiarity Evaluation of Compositions

Given a standard essay library containing M binary strings and a candidate binary composition A, determine the maximum integer L₀ such that A can be segmented into several substrings where the total length of the "familiar" substrings is at least 90% of the length of A. A substring is defined to be familiar if:

\(\text{length} \ge L\)

and it appears as a contiguous substring in at least one string from the library.

The value L₀ is the maximum L for which there exists a segmentation of A satisfying:

\(\sum_{\text{familiar segments}} \text{length} \ge 0.9 \times |A|\)

If no such segmentation exists for any L ≥ 1, then L₀ is defined to be 0.

Example:

Standard Library:
10110
000001110
Candidate Composition A:
1011001100
One valid segmentation when L=4 is: 10110 | 0110 | 0. Here, the segments "10110" (length 5) and "0110" (length 4) are familiar since their lengths are at least 4 and they appear in the library, while "0" is not considered (its length is less than 4). The total familiar length is 5+4=9, which is 90% of 10. For L=5 no valid segmentation exists, hence L₀ = 4 for this case.

inputFormat

The input consists of:

1. An integer M on the first line.
2. The next M lines, each containing a binary string from the standard essay library.
3. The last line contains the candidate composition A (a binary string).

outputFormat

Output a single integer: the value of L₀ as defined in the problem description.

sample

2
10110
000001110
1011001100

4