Tý có một văn bản \(T\) và danh sách K từ cấm. Tý muốn xóa một số ký tự khỏi \(T\) để văn bản sau khi xóa không còn chứa bất kỳ từ cấm nào như một xâu con liên tiếp. Các ký tự còn lại giữ nguyên thứ tự ban đầu. 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 thứ nhất: xâu văn bản \(T\) (\(1 \le |T| $\le 10^5\)), chỉ gồm các chữ cái tiếng Anh in thường a..z.
• Dòng thứ hai: số nguyên \(K\) (\(1 \le K $\le 10^5\), tổng độ dài các từ cấm \(\le 10^5\)).
• K$ dòng tiếp theo: mỗi dòng là một xâu mô tả một từ cấm.

Định dạng đầu ra

• In ra một số nguyên duy nhất là số lượng ký tự ít nhất cần xóa khỏi \(T\).

Ví dụ

Input:

abcabc
2
ab
bc

Output:

2

Giải thích: Xóa ký tự ở vị trí thứ 1 và 4 (vị trí các ký tự 'b') ta được xâu acac, không còn chứa ab hay bc. Số ký tự cần xóa ít nhất là 2.

Ràng buộc & Subtasks