C. Clichés
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Queliton Tarantino is a legendary figure in the world of cinema; his films are known for their sharp dialogue, spectacular plot twists, and above all, for using every possible cliché — always with that ironic touch.

Recently, Queliton has been working on the script for his new masterpiece: a film encoded as a word $$$S$$$, composed only of lowercase letters. Like any impactful screenwriter, he wants to make sure his film is full of classic cinematic clichés — each represented by a word.

But there's a twist: Queliton wants to make one bold move — reversing, at most once, a continuous segment of the film. He knows this trick can turn an ordinary scene into an iconic moment, creating new occurrences of the clichés and, who knows, securing his tenth Palme d'Or.

Your task is to help him determine the maximum number of cliché occurrences he can insert into the film after reversing, at most once, any continuous segment of the script.

Each occurrence counts, even if the same cliché appears multiple times, including overlapping with other occurrences or with itself.

Input

The first line contains the word $$$S$$$ $$$(1 \leq |S| \leq 2000)$$$, the current script of the film.

The second line contains an integer $$$M$$$ $$$(1 \leq M \leq 2000)$$$ — the number of cinematic clichés.

Each of the next $$$M$$$ lines contains a word $$$P_i$$$ $$$(1 \leq |P_i| \leq 2000)$$$, representing a cliché.

The total sum of the lengths of all strings $$$P_i$$$ does not exceed $$$2000$$$.

Output

Print a single integer: the maximum number of cliché occurrences Queliton can achieve after reversing, at most once, any continuous segment of $$$S$$$.

Examples
Input
abbaca
3
cab
bbac
aa
Output
2
Input
abcda
2
da
bc
Output
2
Input
aaaaaabaa
1
abaaa
Output
1
Input
aabababb
4
ab
bab
abab
baba
Output
12