시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 147 22 14 22.581%

문제

이모티콘은 채팅과 이메일에서 단어로 표현할 수 없는 감정을 나타내기 위해 종종 쓰인다. 이는 다양한 면에서 장점이 있지만, 많은 사람들은 이모티콘을 매우 짜증난다고 여기며, 없애고 싶어한다.

세종이가 딱 그렇다. 세종이는 이모티콘을 너무 싫어한 나머지, 전세계의 이메일에서 이모티콘을 없애버릴 계획을 세웠다. 당신은 세종이와 계획을 함께 준비하고 있어서, 세종이를 도와줄 특별한 프로그램을 제작하려고 한다.

프로그램은 제거할 이모티콘의 리스트를 먼저 받는다. 각 이모티콘은 공백(whitespace)을 포함하지 않은 문자열이다. 또한 몇몇 텍스트도 함께 받는다. 이때 프로그램이 해야 할 일은 텍스트의 몇몇 글자를 공백으로 바꿔서 원래 존재하던 모든 이모티콘을 없애버리는 것이다. 원래 텍스트의 한 줄에만 걸쳐 나타나며, 사이에 다른 공백이나 문자열이 끼어 있지 않은 이모티콘만을 이모티콘이라고 할 것이다.

세종이의 계획을 최대한 들통나지 않게 하기 위해, 당신은 공백으로 대체할 문자의 개수를 최소한으로 해야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 여러 줄로 이루어져 있다. 첫 번째 줄은 이모티콘의 개수 N과 텍스트 줄 수 M이 주어지며, 다음 N개의 줄에는 15글자 이하의 비어 있지 않은 문자열인 각 이모티콘이 주어진다. 그 다음 M개의 줄에는 이모티콘을 지울 텍스트들이 주어지며 80글자 이하이다. 1 ≤ N, M ≤ 100 이라 가정해도 좋다.

이모티콘은 영어 대소문자, 숫자, 그리고 특수문자 “!?.,:;-_’#\$%&/=*+(){}[]”(큰따옴표는 포함되지 않음)로만 구성될 수 있다. 텍스트는 여기에 추가로 공백문자까지 포함할 수 있다.

입력의 끝에는 N = M = 0이 주어진다.

출력

각 테스트 케이스에 걸쳐, 한 줄에 하나씩 공백으로 대체해야 할 문자의 최소 개수를 출력한다.

예제 입력 1

4 6
:-)
:-(
(-:
)-:
Hello uncle John! :-) :-D
I am sad or happy? (-:-(?
I feel so happy, my head spins
(-:-)(-:-)(-:-)(-:-) :-) (-: :-)
but then sadness comes :-(
Loves you, Joanna :-)))))
3 1
:)
):
))
:):)):)):)):(:((:(((:):)
0 0

예제 출력 1

11
8
W3sicHJvYmxlbV9pZCI6IjU3MzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJFbW90aWNvbnMgOi0pIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzRcdWJhYThcdWQyZjBcdWNmNThcdWM3NDAgXHVjYzQ0XHVkMzA1XHVhY2ZjIFx1Yzc3NFx1YmE1NFx1Yzc3Y1x1YzVkMFx1YzExYyBcdWIyZThcdWM1YjRcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhYzEwXHVjODE1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODg1XHVjODg1IFx1YzRmMFx1Yzc3OFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1YjJlNFx1YzU5MVx1ZDU1YyBcdWJhNzRcdWM1ZDBcdWMxMWMgXHVjN2E1XHVjODEwXHVjNzc0IFx1Yzc4OFx1YzljMFx1YjljYywgXHViOWNlXHVjNzQwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWM3NzRcdWJhYThcdWQyZjBcdWNmNThcdWM3NDQgXHViOWU0XHVjNmIwIFx1YzlkY1x1Yzk5ZFx1YjA5Y1x1YjJlNFx1YWNlMCBcdWM1ZWNcdWFlMzBcdWJhNzAsIFx1YzVjNlx1YzU2MFx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOFx1Yzg4NVx1Yzc3NFx1YWMwMCBcdWI1MzEgXHVhZGY4XHViODA3XHViMmU0LiBcdWMxMzhcdWM4ODVcdWM3NzRcdWIyOTQgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHVjNzQ0IFx1YjEwOFx1YmIzNCZuYnNwO1x1YzJlYlx1YzViNFx1ZDU1YyBcdWIwOThcdWJhMzhcdWM5YzAsIFx1YzgwNFx1YzEzOFx1YWNjNFx1Yzc1OCBcdWM3NzRcdWJhNTRcdWM3N2NcdWM1ZDBcdWMxMWMgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHVjNzQ0IFx1YzVjNlx1YzU2MFx1YmM4NFx1YjliNCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHVjMTM4XHVjNmUwXHViMmU0LiBcdWIyZjlcdWMyZTBcdWM3NDAmbmJzcDtcdWMxMzhcdWM4ODVcdWM3NzRcdWM2NDAgXHVhY2M0XHVkNjhkXHVjNzQ0IFx1ZDU2OFx1YWVkOCBcdWM5MDBcdWJlNDRcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWI0XHVjMTFjLCBcdWMxMzhcdWM4ODVcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwXHVjOTA0IFx1ZDJiOVx1YmNjNFx1ZDU1YyBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjODFjXHVjNzkxXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1YzgxY1x1YWM3MFx1ZDU2MCBcdWM3NzRcdWJhYThcdWQyZjBcdWNmNThcdWM3NTggXHViOWFjXHVjMmE0XHVkMmI4XHViOTdjIFx1YmEzY1x1YzgwMCBcdWJjMWJcdWIyOTRcdWIyZTQuIFx1YWMwMSBcdWM3NzRcdWJhYThcdWQyZjBcdWNmNThcdWM3NDAgXHVhY2Y1XHViYzMxKHdoaXRlc3BhY2UpXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHViYTg3XHViYTg3IFx1ZDE0ZFx1YzJhNFx1ZDJiOFx1YjNjNCBcdWQ1NjhcdWFlZDggXHViYzFiXHViMjk0XHViMmU0LiBcdWM3NzRcdWI1NGMgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1ZDU3NFx1YzU3YyBcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1ZDE0ZFx1YzJhNFx1ZDJiOFx1Yzc1OCBcdWJhODdcdWJhODcgXHVhZTAwXHVjNzkwXHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWJjMTRcdWFmZDRcdWMxMWMgXHVjNmQwXHViNzk4IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjM1OCBcdWJhYThcdWI0ZTAgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHVjNzQ0IFx1YzVjNlx1YzU2MFx1YmM4NFx1YjlhY1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzZkMFx1Yjc5OCBcdWQxNGRcdWMyYTRcdWQyYjhcdWM3NTggXHVkNTVjIFx1YzkwNFx1YzVkMFx1YjljYyBcdWFjNzhcdWNjZDAgXHViMDk4XHVkMGMwXHViMDk4XHViYTcwLCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViMmU0XHViOTc4IFx1YWNmNVx1YmMzMVx1Yzc3NFx1YjA5OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViMDdjXHVjNWI0IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHViOWNjXHVjNzQ0IFx1Yzc3NFx1YmFhOFx1ZDJmMFx1Y2Y1OFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzhcdWM4ODVcdWM3NzRcdWM3NTggXHVhY2M0XHVkNjhkXHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI0ZTRcdWQxYjVcdWIwOThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQsIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHViMzAwXHVjY2I0XHVkNTYwIFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzNjXHViODVjIFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzVlY1x1YjdlYyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM3NDAgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIFx1ZDE0ZFx1YzJhNFx1ZDJiOCBcdWM5MDQgXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgMTVcdWFlMDBcdWM3OTAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YmU0NFx1YzViNCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3OCBcdWFjMDEgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NzRcdWJhYThcdWQyZjBcdWNmNThcdWM3NDQgXHVjOWMwXHVjNmI4IFx1ZDE0ZFx1YzJhNFx1ZDJiOFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgODBcdWFlMDBcdWM3OTAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiZuYnNwOzEgJmxlOyBOLCBNICZsZTsgMTAwJm5ic3A7XHVjNzc0XHViNzdjIFx1YWMwMFx1YzgxNVx1ZDU3NFx1YjNjNCBcdWM4OGJcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YmFhOFx1ZDJmMFx1Y2Y1OFx1Yzc0MCBcdWM2MDFcdWM1YjQgXHViMzAwXHVjMThjXHViYjM4XHVjNzkwLCBcdWMyMmJcdWM3OTAsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWQyYjlcdWMyMThcdWJiMzhcdWM3OTAmbmJzcDsmbGRxdW87IT8uLDo7LV8mcnNxdW87I1xcJCUmYW1wO1wvPSorKCl7fVtdJnJkcXVvOyhcdWQwNzBcdWI1MzBcdWM2MzRcdWQ0NWNcdWIyOTQgXHVkM2VjXHVkNTY4XHViNDE4XHVjOWMwIFx1YzU0YVx1Yzc0YylcdWI4NWNcdWI5Y2MgXHVhZDZjXHVjMTMxXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDE0ZFx1YzJhNFx1ZDJiOFx1YjI5NCBcdWM1ZWNcdWFlMzBcdWM1ZDAgXHVjZDk0XHVhYzAwXHViODVjIFx1YWNmNVx1YmMzMVx1YmIzOFx1Yzc5MFx1YWU0Y1x1YzljMCBcdWQzZWNcdWQ1NjhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjA1ZFx1YzVkMFx1YjI5NCBOID0gTSA9IDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YWM3OFx1Y2NkMCwgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YjMwMFx1Y2NiNFx1ZDU3NFx1YzU3YyBcdWQ1NjAgXHViYjM4XHVjNzkwXHVjNzU4Jm5ic3A7XHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTczNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVtb3RpY29ucyA6LSkiLCJkZXNjcmlwdGlvbiI6IjxwPkVtb3RpY29ucyBhcmUgdXNlZCBpbiBjaGF0IGFuZCBlLW1haWwgY29udmVyc2F0aW9ucyB0byB0cnkgdG8gZXhwcmVzcyB0aGUgZW1vdGlvbnMgdGhhdCBwcmludGVkIHdvcmRzIGNhbm5vdC4gVGhpcyBtYXkgc2VlbSBsaWtlIGEgbmljZSBmZWF0dXJlIGZvciBtYW55LCBidXQgYSBsb3Qgb2YgcGVvcGxlIGZpbmQgaXQgcmVhbGx5IGFubm95aW5nIGFuZCB3YW50cyB0byBnZXQgcmlkIG9mIGVtb3RpY29ucy48XC9wPlxyXG5cclxuPHA+R2VvcmdlIGlzIG9uZSBvZiB0aG9zZSBwZW9wbGUuIEhlIGhhdGVzIGVtb3RpY29ucyBzbyBiYWQsIHRoYXQgaGUgaXMgcHJlcGFyaW5nIGEgcGxhbiB0byByZW1vdmUgYWxsIGVtb3RpY29ucyBmcm9tIGFsbCBlLW1haWxzIGluIHRoZSB3b3JsZC4gU2luY2UgeW91IHNoYXJlIGhpcyB2aXNpb25hcnkgcGxhbnMsIHlvdSBhcmUgcHJlcGFyaW5nIGEgc3BlY2lhbCBwcm9ncmFtIHRvIGhlbHAgaGltLjxcL3A+XHJcblxyXG48cD5Zb3VyIHByb2dyYW0gd2lsbCByZWNlaXZlIHRoZSBsaXN0IG9mIGVtb3RpY29ucyB0byBwcm9zY3JpYmUuIEVhY2ggZW1vdGljb24gd2lsbCBiZSBhIHN0cmluZyBvZiBjaGFyYWN0ZXJzIG5vdCBpbmNsdWRpbmcgYW55IHdoaXRlc3BhY2UuIFlvdSB3aWxsIGFsc28gcmVjZWl2ZSBzZXZlcmFsIGxpbmVzIG9mIHRleHQuIFdoYXQgeW91IG5lZWQgdG8gZG8gaXMgY2hhbmdlIHNvbWUgY2hhcmFjdGVycyBvZiB0aGUgdGV4dCBpbnRvIHNwYWNlcyB0byBlbnN1cmUgbm8gZW1vdGljb24gaXMgbGVmdCBvbiB0aGUgdGV4dC4gRm9yIGFuIGVtb3RpY29uIHRvIGJlIGNvbnNpZGVyZWQgdG8gYXBwZWFyIGluIHRoZSB0ZXh0IGl0IGhhcyB0byBhcHBlYXIgaW4gYSBzaW5nbGUgbGluZSBhbmQgYmUgbWFkZSBvZiBjb25zZWN1dGl2ZSBjaGFyYWN0ZXJzLjxcL3A+XHJcblxyXG48cD5UbyBoZWxwIEdlb3JnZSZyc3F1bztzIHBsYW4gcmVtYWluIHNlY3JldCBhcyBsb25nIGFzIHBvc3NpYmxlLCB5b3UgbmVlZCB0byBkbyB5b3VyIGpvYiB3aXRoIHRoZSBtaW5pbXVtIHBvc3NpYmxlIGFtb3VudCBvZiBjaGFyYWN0ZXIgY2hhbmdlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2Ygc2V2ZXJhbCBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2Ugd2lsbCBjb250YWluIHR3byBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2U6IE4sIHRoZSBudW1iZXIgb2YgZW1vdGljb25zIHRvIHByb3NjcmliZSwgYW5kIE0sIHRoZSBudW1iZXIgb2YgbGluZXMgdGhlIHRleHQgaGFzLiBUaGUgbmV4dCBOIGxpbmVzIGNvbnRhaW4gb25lIGVtb3RpY29uIGVhY2gsIGEgbm9uLWVtcHR5IHN0cmluZyBvZiBhdCBtb3N0IDE1IGNoYXJhY3RlcnMuIEVhY2ggb2YgdGhlIGxhc3QgTSBsaW5lcyBvZiB0aGUgdGVzdCBjYXNlIGNvbnRhaW5zIGEgbGluZSBvZiB0ZXh0IG9mIGF0IG1vc3QgODAgY2hhcmFjdGVycy4gWW91IGNhbiBhc3N1bWUgMSAmbGU7IE4sIE0gJmxlOyAxMDAuPFwvcD5cclxuXHJcbjxwPlZhbGlkIGlucHV0IGNoYXJhY3RlcnMgZm9yIGVtb3RpY29ucyBhcmUgdXBwZXJjYXNlIGFuZCBsb3dlcmNhc2UgbGV0dGVycywgZGlnaXRzIGFuZCB0aGUgc3ltYm9scyAmbGRxdW87IT8uLDo7LV8mcnNxdW87I1xcJCUmYW1wO1wvPSorKCl7fVtdJnJkcXVvOyAocXVvdGVzIGZvciBjbGFyaXR5KS4gRWFjaCBsaW5lIG9mIHRoZSB0ZXh0IG1heSBjb250YWluIHRoZSBzYW1lIGNoYXJhY3RlcnMgd2l0aCB0aGUgYWRkaXRpb24gb2YgdGhlIHNwYWNlIGNoYXJhY3Rlci48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IGlzIHRlcm1pbmF0ZWQgYnkgTiA9IE0gPSAwLjxcL3A+XHJcblxyXG48cD5UaGUgaW5wdXQgbXVzdCBiZSByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgZXhhY3RseSBvbmUgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgdGhhdCBpbmRpY2F0ZXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGNoYW5nZXMgeW91IG5lZWQgdG8gbWFrZSB0byB0aGUgZW50aXJlIHRleHQgdG8gZW5zdXJlIG5vIGVtb3RpY29uIG9uIHRoZSBsaXN0IGFwcGVhcnMgaW4gaXQuPFwvcD5cclxuXHJcbjxwPlRoZSBvdXRwdXQgbXVzdCBiZSB3cml0dGVuIHRvIHN0YW5kYXJkIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=