Given a string $S$ and $n$ string $T_1, T_2,…,T_m$

Find the longest substring of $S$ that can be created using $T_1, T_2,…T_m$. One string can be used multiple times.

Input

• The first line contains an integer $n$.
• The second line contains string $S$.
• The next $n$ lines, the $i^{th}$ line contains string $T_i$.

Output

• Print the length of the longest substring can be formed from $T_1, T_2,…,T_n$.

Constraints

• $1 \le n , |S| \le 2000$.
• $\sum{|T_i|} \le 10^5$.

Example

Input:

3
abbac
ac
b
a

Output:

5