Phân tích tiếng cười

Giáo sư Thuấn có nhiều công trình nghiên cứu khoa học nổi tiếng. Một trong các công trình gây nhiều tiếng vang nhất là công trình "Phân tích tiếng cười". Trong nghiên cứu này, giáo sư đã phân tích tiếng nói của con người và từ đó trích ra tiếng cười. Giáo sư đã phát triển các phần mềm cho phép chuyển đổi tiếng nói của con người thành văn bản.

Giáo sư xét chuỗi tiếng cười là một xâu gồm các chữ cái a, b, c, h, và phải được ghép từ các xâu thuộc tập xâu $p_1,p_2,\dots ,p_n$ (mỗi xâu có thể được dùng nhiều lần, các xâu khác nhau có thể được ghép xen kẽ nhau), trong đó các xâu $p_1,p_2,\dots ,p_n$ là các xâu mô tả tiếng cười đã được giáo sư xây dựng. Ví dụ, nếu tập xâu mô tả tiếng cười là ha và a, thì xâu ahahaha và a là tiếng cười, còn abacaba và hh không phải.

Yêu cầu: Bạn được cho một xâu $s$ là xâu được chuyển đổi từ tiếng nói và tập các xâu $p_1,p_2,\dots ,p_n$. Tìm độ dài của xâu con dài nhất (gồm các kí tự liên tiếp) của xâu $s$ có thể được xét như là chuỗi tiếng cười. Nếu không có xâu con nào như vậy, in ra $0$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$;
• Dòng thứ hai chứa xâu $s$;
• $n$ dòng tiếp theo, dòng thứ $i$ chứa xâu $p_i$ ($i=1,2,\dots ,n$), các xâu này có độ dài không vượt quá $30$.

Các xâu chỉ gồm các chữ cái a, b, c, h.

Dữ liệu ra

In ra một số nguyên duy nhất là độ dài của xâu con dài nhất của $s$ có thể được xét như là chuỗi tiếng cười.

Ràng buộc

• $1\le n\le 1000$.
• $1\le |s|\le {10}^5$.
• $1\le |p_i|\le 30$ ($i=1,2,\dots ,n$).
• Các xâu chỉ gồm các chữ cái a, b, c, h.

Subtasks

• Subtask 1 ($20\%$ số test): $n=1$ và $|s|\le 100$.
• Subtask 2 ($20\%$ số test): $n=1$ và $|s|\le {10}^5$.
• Subtask 3 ($20\%$ số test): $n=2$ và $|s|\le 30$.
• Subtask 4 ($20\%$ số test): $n\le 100$ và $|s|\le 100$.
• Subtask 5 ($20\%$ số test): $n\le 1000$ và $|s|\le {10}^5$.

Ví dụ