Вам дано рядок ~s~, що складається з малих латинських літер. Також у вас є ~m~ рядків ~t_i~, для яких можна застосувати операцію скорочення.

За одну операцію ви можете вибрати підрядок в ~s~ який дорівнює ~t_i~ та замінити його одним символом '*'. Ви можете виконувати операцію безліч разів(можливо жодного).

Якої мінімальної довжини може стати строка в результаті виконання всіх операцій?

Input

На ввід подається рядок ~s~(~1 \le |s| \le 10^4~) та число ~m~(~1 \le m \le 50~) — кількість скороченнь.

Далі вводяться ~m~ рядків ~t_i~(~1 \le i \le m, 1 \le |t_i| \le 10^4~)

Output

Виведіть одне число — відповідь до задачі.

Sample Input 1

qwertyui
2
qwer
qwertyuio

Sample Output 1

5