Tý có một văn bản \(T\) và danh sách từ cấm. Tý muốn xóa một số ký tự khỏi \(T\) để văn bản không còn chứa bất kỳ từ cấm nào. Các ký tự còn lại giữ nguyên thứ tự. Hãy giúp Tý tìm số ký tự ít nhất cần xóa!

Định dạng đầu vào

• Dòng đầu: xâu \(T\) (\(1 \le |T| \le 10^5\)), gồm chữ cái in thường a..z.
• Dòng hai: số nguyên \(K\) (\(1 \le K \le 10^5\), tổng độ dài từ cấm \le 10^5~).
• ~K dòng tiếp theo: mỗi dòng là một từ cấm.

Định dạng đầu ra

• In ra số ký tự ít nhất cần xóa.

Ví dụ

Input:

abcabc
2
ab
bc

Output:

2

Giải thích: Xóa ký tự ở vị trí 1 và 3 (0-indexed) ta được ac, không chứa ab hay bc.

Ràng buộc