시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 14 8 6 54.545%

문제

이 세상에는 남규어와 재혁어가 있다. 그러나 언제부터인가 그 중간 단계인 상학어가 발생하였다.

상학어에 속하는 단어는 다음과 같이 만들어진다. 남규어에 속하는 단어 중 하나를 골라 길이 1 이상인 접두사를 하나 고른다. 재혁어에 속하는 단어 중 하나를 골라 길이 1 이상인 접미사를 하나 고른다. 둘을 남규어-재혁어 순으로 이어붙인다. 이렇게 하면 상학어 단어가 완성된다. 참 쉽죠? 예를 들면 남규어 단어 "abc"와 재혁어 단어 "de"가 있으면 "ae", "ade", "abe", "abde", "abce", "abcde" 등의 상학어 단어를 만들 수 있지만, "bce", "ace", "abc" 등은 만들 수 없다.

물론 단어를 막 만들다 보니 때로는 의미를 부여하기 힘들 수도 있지만 그런 건 아무래도 좋다. 남규어 사전과 재혁어 사전이 주어질 때, 중복되지 않는 상학어 단어가 최대 몇 개나 만들어질 수 있는지 구하는 프로그램을 작성하시오. 예를 들면 남규어 단어 "ab", "abc"와 재혁어 단어 "cd", "d"가 있다면 "abcd"는 2번 만들어지지만 중복되므로 한 번만 세야 한다.

입력

입력은 여러 개의 테스트 케이스로 주어져 있으며, "0 0"으로 끝난다. 각 테스트 케이스는 다음과 같은 형식으로 이루어져 있다.

첫째 줄에 남규어 단어의 개수 P, 재혁어 단어의 개수 S가 주어진다. (1 ≤ P, S ≤ 1000)

그 다음 P개의 줄에 남규어 단어가 각각 하나씩, 그 다음 S개의 줄에 재혁어 단어가 각각 하나씩 주어진다. 단어는 1글자 이상 1,000글자 이하의 영어 소문자로만 이루어져 있다. 한 언어 안에 중복되는 단어는 없으며, 한 언어 안에 속하는 단어의 글자 합은 최대 105글자다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 만들 수 있는 상학어 개수를 출력한다.

예제 입력

3 3
mais
grande
mundo
mas
grande
mundo
1 5
a
aaaaa
aaaaaa
aaaaaaa
a
aaaaaaaaa
1 1
abc
abc
0 0

예제 출력

182
9
8

힌트