시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 35 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글자다.

출력

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

예제 입력 1

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

예제 출력 1

182
9
8
W3sicHJvYmxlbV9pZCI6IjU2ODMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWQ1NTlcdWM1YjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc3NCBcdWMxMzhcdWMwYzFcdWM1ZDBcdWIyOTQgXHViMGE4XHVhZGRjXHVjNWI0XHVjNjQwIFx1YzdhY1x1ZDYwMVx1YzViNFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCBcdWM1YjhcdWM4MWNcdWJkODBcdWQxMzBcdWM3NzhcdWFjMDAgXHVhZGY4IFx1YzkxMVx1YWMwNCBcdWIyZThcdWFjYzRcdWM3NzggXHVjMGMxXHVkNTU5XHVjNWI0XHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU1OFx1YzYwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVkNTU5XHVjNWI0XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWIyZThcdWM1YjRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjBhOFx1YWRkY1x1YzViNFx1YzVkMCBcdWMxOGRcdWQ1NThcdWIyOTQgXHViMmU4XHVjNWI0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2U4XHViNzdjIFx1YWUzOFx1Yzc3NCAxIFx1Yzc3NFx1YzBjMVx1Yzc3OCBcdWM4MTFcdWI0NTBcdWMwYWNcdWI5N2MgXHVkNTU4XHViMDk4IFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVjN2FjXHVkNjAxXHVjNWI0XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWIyZThcdWM1YjQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjZThcdWI3N2MgXHVhZTM4XHVjNzc0IDEgXHVjNzc0XHVjMGMxXHVjNzc4IFx1YzgxMVx1YmJmOFx1YzBhY1x1Yjk3YyBcdWQ1NThcdWIwOTggXHVhY2UwXHViOTc4XHViMmU0LiBcdWI0NThcdWM3NDQgXHViMGE4XHVhZGRjXHVjNWI0LVx1YzdhY1x1ZDYwMVx1YzViNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHVjNzc0XHVjNWI0XHViZDk5XHVjNzc4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTU4XHViYTc0IFx1YzBjMVx1ZDU1OVx1YzViNCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjNjQ0XHVjMTMxXHViNDFjXHViMmU0LiBcdWNjMzggXHVjMjdkXHVjOGUwPyBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0IFx1YjBhOFx1YWRkY1x1YzViNCBcdWIyZThcdWM1YjQgJnF1b3Q7YWJjJnF1b3Q7XHVjNjQwIFx1YzdhY1x1ZDYwMVx1YzViNCBcdWIyZThcdWM1YjQgJnF1b3Q7ZGUmcXVvdDtcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTc0ICZxdW90O2FlJnF1b3Q7LCAmcXVvdDthZGUmcXVvdDssICZxdW90O2FiZSZxdW90OywgJnF1b3Q7YWJkZSZxdW90OywgJnF1b3Q7YWJjZSZxdW90OywgJnF1b3Q7YWJjZGUmcXVvdDsgXHViNGYxXHVjNzU4IFx1YzBjMVx1ZDU1OVx1YzViNCBcdWIyZThcdWM1YjRcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWM5YzBcdWI5Y2MsICZxdW90O2JjZSZxdW90OywgJnF1b3Q7YWNlJnF1b3Q7LCAmcXVvdDthYmMmcXVvdDsgXHViNGYxXHVjNzQwIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiM2NcdWI4NjAgXHViMmU4XHVjNWI0XHViOTdjIFx1YjljOSBcdWI5Y2NcdWI0ZTRcdWIyZTQgXHViY2Y0XHViMmM4IFx1YjU0Y1x1Yjg1Y1x1YjI5NCBcdWM3NThcdWJiZjhcdWI5N2MgXHViZDgwXHVjNWVjXHVkNTU4XHVhZTMwIFx1ZDc5OFx1YjRlNCBcdWMyMThcdWIzYzQgXHVjNzg4XHVjOWMwXHViOWNjIFx1YWRmOFx1YjdmMCBcdWFjNzQgXHVjNTQ0XHViYjM0XHViNzk4XHViM2M0IFx1Yzg4Ylx1YjJlNC4gXHViMGE4XHVhZGRjXHVjNWI0IFx1YzBhY1x1YzgwNFx1YWNmYyBcdWM3YWNcdWQ2MDFcdWM1YjQgXHVjMGFjXHVjODA0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMGMxXHVkNTU5XHVjNWI0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YWMxY1x1YjA5OCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCBcdWIwYThcdWFkZGNcdWM1YjQgXHViMmU4XHVjNWI0ICZxdW90O2FiJnF1b3Q7LCAmcXVvdDthYmMmcXVvdDtcdWM2NDAgXHVjN2FjXHVkNjAxXHVjNWI0IFx1YjJlOFx1YzViNCAmcXVvdDtjZCZxdW90OywgJnF1b3Q7ZCZxdW90O1x1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQgJnF1b3Q7YWJjZCZxdW90O1x1YjI5NCAyXHViYzg4IFx1YjljY1x1YjRlNFx1YzViNFx1YzljMFx1YzljMFx1YjljYyBcdWM5MTFcdWJjZjVcdWI0MThcdWJiYzBcdWI4NWMgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWMxMzhcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcIjAgMFwiXHVjNzNjXHViODVjIFx1YjA1ZFx1YjA5Y1x1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMGE4XHVhZGRjXHVjNWI0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMTggUCwgXHVjN2FjXHVkNjAxXHVjNWI0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMTggU1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxIFx1MjI2NCBQLCBTIFx1MjI2NCAxMDAwKTxcL3A+PHA+XHVhZGY4IFx1YjJlNFx1Yzc0YyBQXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWIwYThcdWFkZGNcdWM1YjQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YWMwMVx1YWMwMSBcdWQ1NThcdWIwOThcdWM1MjksIFx1YWRmOCBcdWIyZTRcdWM3NGMgU1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjN2FjXHVkNjAxXHVjNWI0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWFjMDFcdWFjMDEgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IDFcdWFlMDBcdWM3OTAgXHVjNzc0XHVjMGMxIDEsMDAwXHVhZTAwXHVjNzkwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM2MDFcdWM1YjQgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDU1YyBcdWM1YjhcdWM1YjQgXHVjNTQ4XHVjNWQwIFx1YzkxMVx1YmNmNVx1YjQxOFx1YjI5NCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjNWM2XHVjNzNjXHViYTcwLCBcdWQ1NWMgXHVjNWI4XHVjNWI0IFx1YzU0OFx1YzVkMCBcdWMxOGRcdWQ1NThcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWUwMFx1Yzc5MCBcdWQ1NjlcdWM3NDAgXHVjZDVjXHViMzAwIDEwPHN1cD41PFwvc3VwPlx1YWUwMFx1Yzc5MFx1YjJlNC48YnI+PFwvcD4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWQ1NTlcdWM1YjQgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48YnI+PFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NjgzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGljY2lvblx1MDBlMXJpbyBQb3J0dVx1MDBmMW9sIiwiZGVzY3JpcHRpb24iOiI8cD5Qb3J0dSZudGlsZGU7b2wgaXMgYSBzcGVjaWFsIGxhbmd1YWdlIHRoYXQgd2FzIG5hdHVyYWxseSBkZXZlbG9wZWQgaW4gTGF0aW4gQW1lcmljYS4gU2luY2UgYWxtb3N0IGhhbGYgb2YgTGF0aW4gQW1lcmljYSBzcGVha3MgUG9ydHVndWVzZSAoUG9ydHVndSZlY2lyYztzKSBhbmQgYWxtb3N0IGhhbGYgc3BlYWtzIFNwYW5pc2ggKEVzcGEmbnRpbGRlO29sKSwgdGhlIG1peGluZyBvZiBib3RoIGxhbmd1YWdlcyBpcyBuYXR1cmFsLjxcL3A+XHJcblxyXG48cD5FYWNoIHdvcmQgaW4gUG9ydHUmbnRpbGRlO29sIGlzIG1hZGUgYnkgdGFraW5nIGEgbm9uLWVtcHR5IHByZWZpeCBvZiBhIFBvcnR1Z3Vlc2Ugd29yZCBhbmQgYSBub25lbXB0eSBzdWZmaXggb2YgYSBTcGFuaXNoIHdvcmQsIGFuZCBjb25jYXRlbmF0aW5nIHRoZW0gdG9nZXRoZXIuIEEgcHJlZml4IG9mIGEgd29yZCBpcyBhbnkgd29yZCB0aGF0IGNhbiBiZSBvYnRhaW5lZCBieSBlcmFzaW5nIHplcm8gb3IgbW9yZSBjaGFyYWN0ZXJzIGZyb20gaXRzIHJpZ2h0IGVuZC4gQSBzdWZmaXggb2YgYSB3b3JkIGlzIGFueSB3b3JkIHRoYXQgY2FuIGJlIG9idGFpbmVkIGJ5IGVyYXNpbmcgemVybyBvciBtb3JlIGNoYXJhY3RlcnMgZnJvbSBpdHMgbGVmdCBlbmQuIFRoZSBuYW1lIG9mIHRoZSBsYW5ndWFnZSBpdHNlbGYgY29tZXMgZnJvbSB0YWtpbmcgYSBwcmVmaXggb2YgdGhlIHdvcmQgJmxkcXVvO1BvcnR1Z3UmZWNpcmM7cyZyZHF1bzsgKFBvcnR1KSBhbmQgYSBzdWZmaXggb2YgdGhlIHdvcmQgJmxkcXVvO0VzcGEmbnRpbGRlO29sJnJkcXVvOyAoJm50aWxkZTtvbCksIGFuZCBjb25jYXRlbmF0aW5nIHRoZW0uPFwvcD5cclxuXHJcbjxwPk9mIGNvdXJzZSwgbm90IGV2ZXJ5IHBvc3NpYmxlIHdheSBvZiBjb21iaW5pbmcgdHdvIHdvcmRzIHdpbGwgcmVzdWx0IGluIHNvbWV0aGluZyBtZWFuaW5nZnVsLCBvciBldmVuIHByb25vdW5jZWFibGUsIGJ1dCB0aGF0IGlzIG5vdCBpbXBvcnRhbnQuIFdlIHdhbnQgeW91IHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBjb3VudCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBQb3J0dSZudGlsZGU7b2wgd29yZHMuPFwvcD5cclxuXHJcbjxwPllvdSB3aWxsIGJlIGdpdmVuIHR3byBub24tZW1wdHkgc2V0cyBvZiB3b3JkcyB0byB0ZXN0IHlvdXIgcHJvZ3JhbS4gVGhlIGZpcnN0IHNldCB3aWxsIHJlcHJlc2VudCBQb3J0dWd1ZXNlIHdvcmRzIGFuZCB0aGUgc2Vjb25kIHNldCB3aWxsIHJlcHJlc2VudCBTcGFuaXNoIHdvcmRzLiBZb3UgbmVlZCB0byBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgUG9ydHUmbnRpbGRlO29sIHdvcmRzIHRoYXQgY2FuIGJlIG1hZGUgdXNpbmcgdGhlIHByZWZpeCBhbmQgc3VmZml4IHJ1bGUgZGVzY3JpYmVkIGFib3ZlLiBOb3RlIHRoYXQgdGhlIHNhbWUgd29yZCBtYXkgYmUgY29uc3RydWN0ZWQgaW4gc2V2ZXJhbCB3YXlzLCBidXQgaXQgc3RpbGwgbmVlZHMgdG8gYmUgY291bnRlZCBhcyBvbmUuIEFsc28gbm90ZSB0aGF0IHRoZSBpbnB1dCBzZXRzIGFyZSBqdXN0IHRvIHRlc3QgeW91ciBwcm9ncmFtLCBzbyB0aGV5IGRvIG5vdCBuZWVkIHRvIGJlIG1hZGUgb3V0IG9mIGFjdHVhbCBQb3J0dWd1ZXNlIG9yIFNwYW5pc2ggd29yZHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY2FzZSBpcyBkZXNjcmliZWQgdXNpbmcgc2V2ZXJhbCBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIFAgYW5kIFMgcmVwcmVzZW50aW5nIHJlc3BlY3RpdmVseSB0aGUgbnVtYmVyIG9mIFBvcnR1Z3Vlc2Ugd29yZHMgYW5kIHRoZSBudW1iZXIgb2YgU3BhbmlzaCB3b3JkcyAoMSAmbGU7IFAsIFMgJmxlOyAxMDAwKS4gRWFjaCBvZiB0aGUgbmV4dCBQIGxpbmVzIGNvbnRhaW5zIGEgUG9ydHVndWVzZSB3b3JkLCBhbmQgYWZ0ZXIgdGhhdCBlYWNoIG9mIHRoZSBuZXh0IFMgbGluZXMgY29udGFpbnMgYSBTcGFuaXNoIHdvcmQuIEVhY2ggd29yZCBpcyBhIG5vbi1lbXB0eSBzdHJpbmcgb2YgYXQgbW9zdCAxMDAwIGNoYXJhY3RlcnM7IGVhY2ggY2hhcmFjdGVyIGlzIG9uZSBvZiB0aGUgMjYgc3RhbmRhcmQgbG93ZXJjYXNlIGxldHRlcnMgKGZyb20gJmxzcXVvO2EmcnNxdW87IHRvICZsc3F1bzt6JnJzcXVvOykuIFlvdSBtYXkgYXNzdW1lIHRoYXQgd2l0aGluIGVhY2ggdGVzdCBjYXNlIG5vIHR3byBQb3J0dWd1ZXNlIHdvcmRzIGFyZSB0aGUgc2FtZSwgYW5kIHRoYXQgdGhlIHN1bSBvZiB0aGUgbGVuZ3RocyBvZiBhbGwgdGhlIFBvcnR1Z3Vlc2Ugd29yZHMgaXMgYXQgbW9zdCAxMDxzdXA+NTxcL3N1cD4uIFRoZSBzYW1lIGhvbGRzIGZvciB0aGUgU3BhbmlzaCB3b3Jkcy48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgdGVzdCBjYXNlIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIHR3byB6ZXJvcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IGEgbGluZSB3aXRoIGFuIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdvcmRzIHRoYXQgY2FuIGJlIGNvbnN0cnVjdGVkIGJ5IGNvbmNhdGVuYXRpbmcgYSBub24tZW1wdHkgcHJlZml4IG9mIGEgd29yZCBpbiB0aGUgZmlyc3Qgc2V0IChQb3J0dWd1ZXNlIHdvcmRzKSBhbmQgYSBub24tZW1wdHkgc3VmZml4IG9mIGEgd29yZCBpbiB0aGUgc2Vjb25kIHNldCAoU3BhbmlzaCB3b3JkcykuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d