Ghép xâu thành dãy con

Cho một tập gồm $n$ xâu ký tự (chỉ gồm các chữ cái Latin thường) và một xâu yêu thích $s$.

Bạn được phép chọn một số xâu từ tập (mỗi xâu có thể được chọn nhiều lần, hoặc không chọn) rồi viết chúng liên tiếp nhau thành một xâu lớn. Hãy tìm số lượng xâu tối thiểu cần chọn (tính cả số lần lặp) sao cho $s$ là dãy con của xâu lớn thu được.

Một xâu $p$ là dãy con của xâu $q$ nếu có thể thu được $p$ bằng cách xóa đi một số (có thể là $0$) ký tự khỏi $q$ mà không thay đổi thứ tự các ký tự còn lại. Ví dụ, trong xâu "abcd" thì "ad", "acd", "abcd" là các dãy con, còn "ba", "abdc" thì không.

Nếu không thể tạo ra $s$ bằng cách trên, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số lượng xâu trong tập.
• $n$ dòng tiếp theo, mỗi dòng chứa một xâu khác rỗng gồm các chữ cái Latin thường. Các xâu trong tập có thể trùng nhau.
• Dòng cuối chứa xâu $s$ khác rỗng gồm các chữ cái Latin thường.

Dữ liệu ra

In ra một số nguyên — số lượng xâu tối thiểu cần chọn để $s$ là dãy con của xâu ghép, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le n\le 50$
• Độ dài mỗi xâu trong tập không vượt quá $50$.
• Độ dài của $s$ không vượt quá $2500$.

Ví dụ