Maximum String Pasting

Time limit1sMemory limit128 MB

Summary
Given a long string and up to 500 short patterns, find all their occurrences and select non-overlapping intervals to maximize total covered length via DP.
Level

Medium7 of 10

Topics
String matching, Dynamic programming, Greedy
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

  1. Example 1

    Input
    aabcc
2
aab
bcc
    Expected output
    3

  2. Example 2

    Input
    abcdefghijklmnopqrstuvwxyz
4
abcdefg
bcdefghijkl
cdefghij
mnopqrstuvwxyz
    Expected output
    25