Cho xâu \(X\) và tập hợp \(S\) gồm \(n\) xâu \(S_i\). Thực hiện rút gọn xâu \(X\) bằng tập hợp \(S\) như sau:

• Nếu \(S_i\) là xâu con của \(X\) thì có thể xóa hoặc không.
• Sau mỗi lần xóa, bạn sẽ nhận được một xâu mới bằng cách nối phần ở bên trái và phải của xâu con đã xóa.

Yêu cầu:

• Hãy thực hiện rút gọn xâu \(X\) để xâu mới có độ dài nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa xâu \(X\) \((len(X) \le 250)\)
• Dòng thứ hai chứa số nguyên \(n\) \((0 \lt n \le 30)\)
• \(N\) dòng tiếp theo, dòng thứ i chứa xâu \(S_i\) \((len(S_i) \le 20)\)

Dữ liệu ra

• Độ dài nhỏ nhất của xâu mới sau khi thực hiện rút gọn

Input 1

aaabccd
3
abc
ac
aaa

Output 1

2

Giải thích:

• Lần 1: xóa xâu \(abc\), kết quả xâu mới là \(aacd\)
• Lần 2: xóa xâu \(ac\), kết quả xâu mới là \(ad\) có độ dài \(2\)