시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB292943929214.328%

문제

어떤 긴 문자열이 주어지고 여러 개의 짧은 문자열들이 주어질때 이때 짧은 문자열을 긴 문자열에 붙여 넣을때 가장 길게 붙여 넣는 경우를 찾아라. 단 이때 짧은 문자열들끼리는 교차 할 수 없다. (‘aabbc'  에  'aab' 와 'bbc' 둘 다 붙여 넣는 것은 불가능하다.) 또, 짧은 문자열은 여러 번 사용할 수 있다.

입력

첫 번째 줄에는 가장 긴 문자열이 주어지고 두 번째 줄에는 짧은 문자열의 숫자 N(1 ≤ N ≤ 500)이 입력으로 주어진다. 세 번째 줄부터 N개의 줄에는 짧은 문자열이 주어진다.

가장 긴 문자열의 길이 L은 (1 ≤ L ≤ 100,000) 짧은 문자열의 길이 l은 (1 ≤ l ≤ 10,000)이다. 모든 문자열은 알파벳 대/소문자로만 이루어져 있다.

출력

붙여 넣은 짧은 문자열들의 길이의 총합을 출력한다.

예제 입력 1

aabcc
2
aab
bcc

예제 출력 1

3

예제 입력 2

abcdefghijklmnopqrstuvwxyz
4
abcdefg
bcdefghijkl
cdefghij
mnopqrstuvwxyz

예제 출력 2

25

출처