Cho xâu \(S\) và \(n\) xâu \(T_1,T_2,...T_m\)

Tìm xâu con dài nhất của \(S\) mà có thể được ghép bởi các xâu \(T_1,T_2,...T_m\). Một xâu có thể được sử dụng nhiều lần.

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên \(n\)
• Dòng thứ hai là xâu \(S\)
• \(n\) dòng tiếp theo mỗi dòng gồm \(1\) xâu \(T_i\)

Dữ liệu ra

• In ra độ dài xâu con dài nhất của \(S\) có thể tạo ra được bằng cách ghép các xâu trong \(T\).

Ràng buộc

• \(1 \le n, |S| \le 3000\)
• \(\sum |T_i| \le 10^5\)

Input 1

3
abbac
ac
b
a

Output 1

5