Maximum String Pasting

You are given one long string and several short strings. If a short string exactly matches a contiguous substring of the long string, you may paste that short string onto that interval. The chosen intervals must not overlap, and each short string may be used multiple times.

Find the maximum possible sum of the lengths of the pasted short strings.

The first line contains the long string. The second line contains an integer N, the number of short strings. Each of the next N lines contains one short string.

Let L be the length of the long string. 1 ≤ L ≤ 100,000. Let l be the length of a short string. 1 ≤ l ≤ 10,000. Also, 1 ≤ N ≤ 500. All strings consist only of uppercase and lowercase English letters.

Print the maximum possible total length of the short strings pasted onto the selected intervals.