시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 2 2 66.667%

문제

프로그래밍 대회는 대회마다 나오는 문제의 유형이 다르다. 예를 들어, TopCoder는 배열의 최대 크기가 50이다. 또, IOI는 아이들이 참가하는 대회이기 때문에 Suffix Tree문제는 나오지 않는다.

우현이는 서로 다른 N개 프로그래밍 대회의 문제 출제자이다. 각 대회는 필요한 문제의 수가 서로 다르다. 예를 들어, ACM-ICPC 스타일의 대회는 보통 10 문제가 필요하고, Topcoder SRM은 5문제가 필요하다.

다행히도 우현이는 M개 문제를 미리 준비해두었다. 또, 각 문제 별로 어떤 대회에서 사용할 수 있는지도 정해놓았다.

모든 대회를 전부 동시에 진행할 때, 몇 개의 대회를 진행할 수 있을까? 대회를 진행하려면 필요한 문제수 만큼 모두 준비해야 한다. 또, 한 문제를 서로 다른 대회에 출제할 수 없다.

입력

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

테스트 케이스의 첫째 줄에는 대회의 수 N과 준비한 문제의 수 M이 주어진다. (1 ≤ N ≤ 15, 0 ≤ M ≤ 50) 다음 N개의 줄에는 각 대회의 이름과 대회를 열기 위해 필요한 문제 수가 주어진다. 대회의 이름은 알파벳 대소문자와 숫자로 이루어져 있고, 100자를 넘지 않는다. 또, 알파벳 대소문자를 구분한다. 필요한 문제 수는 100개를 넘지 않는다.

다음 M개의 줄에는 각 문제를 낼 수 있는 대회의 이름이 공백으로 구분되어 주어진다. 만약, 어떤 문제를 낼 수 있는 대회가 없을 때는 비어있다.

입력의 마지막 줄에는 0 두 개가 주어진다.

출력

각 테스트 케이스에 대해서, 동시에 개최할 수 있는 대회의 수를 케이스 번호와 함께 출력한다. 예제 출력 형식을 참고한다.

예제 입력 1

4 5
IOI 3
IPSC 2
TopCoder 2
SEERC 10
IOI
IPSC TopCoder
IOI IPSC
IOI IPSC
TopCoder SEERC
1 1
SampleContest 1
SampleContest
0 0

예제 출력 1

Case #1: 2
Case #2: 1
W3sicHJvYmxlbV9pZCI6IjM3MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHViMzAwXHVkNjhjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHViMzAwXHVkNjhjXHViMjk0IFx1YjMwMFx1ZDY4Y1x1YjljOFx1YjJlNCBcdWIwOThcdWM2MjRcdWIyOTQgXHViYjM4XHVjODFjXHVjNzU4IFx1YzcyMFx1ZDYxNVx1Yzc3NCBcdWIyZTRcdWI5NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFRvcENvZGVyXHViMjk0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVkMDZjXHVhZTMwXHVhYzAwIDUwXHVjNzc0XHViMmU0LiBcdWI2MTAsIElPSVx1YjI5NCBcdWM1NDRcdWM3NzRcdWI0ZTRcdWM3NzQgXHVjYzM4XHVhYzAwXHVkNTU4XHViMjk0IFx1YjMwMFx1ZDY4Y1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgU3VmZml4IFRyZWVcdWJiMzhcdWM4MWNcdWIyOTQgXHViMDk4XHVjNjI0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHVkNjA0XHVjNzc0XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggTlx1YWMxYyBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHViMzAwXHVkNjhjXHVjNzU4IFx1YmIzOFx1YzgxYyBcdWNkOWNcdWM4MWNcdWM3OTBcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWIzMDBcdWQ2OGNcdWIyOTQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgQUNNLUlDUEMgXHVjMmE0XHVkMGMwXHVjNzdjXHVjNzU4IFx1YjMwMFx1ZDY4Y1x1YjI5NCBcdWJjZjRcdWQxYjUgMTAgXHViYjM4XHVjODFjXHVhYzAwIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YWNlMCwgVG9wY29kZXIgU1JNXHVjNzQwIDVcdWJiMzhcdWM4MWNcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWQ1ODlcdWQ3ODhcdWIzYzQgXHVjNmIwXHVkNjA0XHVjNzc0XHViMjk0IE1cdWFjMWMgXHViYjM4XHVjODFjXHViOTdjIFx1YmJmOFx1YjlhYyBcdWM5MDBcdWJlNDRcdWQ1NzRcdWI0NTBcdWM1YzhcdWIyZTQuIFx1YjYxMCwgXHVhYzAxIFx1YmIzOFx1YzgxYyBcdWJjYzRcdWI4NWMgXHVjNWI0XHViNWE0IFx1YjMwMFx1ZDY4Y1x1YzVkMFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMFx1YjNjNCBcdWM4MTVcdWQ1NzRcdWIxOTNcdWM1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVjODA0XHViZDgwIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM5YzRcdWQ1ODlcdWQ1NjAgXHViNTRjLCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YjMwMFx1ZDY4Y1x1Yjk3YyBcdWM5YzRcdWQ1ODlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz8gXHViMzAwXHVkNjhjXHViOTdjIFx1YzljNFx1ZDU4OVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViYjM4XHVjODFjXHVjMjE4IFx1YjljY1x1ZDA3YyBcdWJhYThcdWI0NTAgXHVjOTAwXHViZTQ0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWQ1NWMgXHViYjM4XHVjODFjXHViOTdjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViMzAwXHVkNjhjXHVjNWQwIFx1Y2Q5Y1x1YzgxY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMzAwXHVkNjhjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YzkwMFx1YmU0NFx1ZDU1YyBcdWJiMzhcdWM4MWNcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxNSwgMCAmbGU7IE0gJmxlOyA1MCkgXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWIzMDBcdWQ2OGNcdWM3NTggXHVjNzc0XHViOTg0XHVhY2ZjIFx1YjMwMFx1ZDY4Y1x1Yjk3YyBcdWM1ZjRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWJiMzhcdWM4MWMgXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMzAwXHVkNjhjXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHVjMThjXHViYjM4XHVjNzkwXHVjNjQwIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCAxMDBcdWM3OTBcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViNjEwLCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHVjMThjXHViYjM4XHVjNzkwXHViOTdjIFx1YWQ2Y1x1YmQ4NFx1ZDU1Y1x1YjJlNC4gXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YmIzOFx1YzgxYyBcdWMyMThcdWIyOTQgMTAwXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViYjM4XHVjODFjXHViOTdjIFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjMwMFx1ZDY4Y1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjNWI0XHViNWE0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIzMDBcdWQ2OGNcdWFjMDAgXHVjNWM2XHVjNzQ0IFx1YjU0Y1x1YjI5NCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDAgXHViNDUwIFx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVhYzFjXHVjZDVjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMzAwXHVkNjhjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHVjNjQwIFx1ZDU2OFx1YWVkOCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1YzgxYyBcdWNkOWNcdWI4MjUgXHVkNjE1XHVjMmRkXHVjNzQ0IFx1Y2MzOFx1YWNlMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM3MjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcm9ibGVtc2V0dGluZyIsImRlc2NyaXB0aW9uIjoiPHA+SXQmIzM5O3Mgd2VsbC1rbm93biB0aGF0IGRpZmZlcmVudCBwcm9ncmFtbWluZyBjb250ZXN0cyByZXF1aXJlIGRpZmZlcmVudCBraW5kIG9mIHByb2JsZW1zLiBGb3IgZXhhbXBsZSwgbWF4aW1hbCBhcnJheSBzaXplIGZvciBUb3BDb2RlciBwcm9ibGVtIGlzIG9ubHkgNTAsIGFuZCB5b3UgZGVmaW5pdGVseSBjYW4gbm90IGdpdmUgYSBTdWZmaXggVHJlZSBwcm9ibGVtIHRvIElPSSBiZWNhdXNlIGNoaWxkcmVuIHdpbGwgbm90IGhhdmUgYSBjaGFuY2UgdG8gc29sdmUgaXQgKGV4Y2VwdCBvZiBzb21lIHRvdXJpc3RpYy1pbmNsaW5lZCBvbmVzKS4gVGh1cyBub3QgZXZlcnkgcHJvYmxlbSBpcyBhY2NlcHRhYmxlIGZvciBldmVyeSBjb250ZXN0LjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHByZXBhcmluZyBwcm9ibGVtc2V0cyBmb3IgTiBkaWZmZXJlbnQgY29udGVzdHMuIFRoZXNlIGNvbnRlc3RzIHJlcXVpcmUgZGlmZmVyZW50IG51bWJlciBvZiBwcm9ibGVtcywgZGVwZW5kaW5nIG9mIHR5cGUuIEZvciBleGFtcGxlLCBBQ00gSUNQQyBzdHlsZSBwcm9ibGVtc2V0IHVzdWFsbHkgaGFzIDEwIHByb2JsZW1zLCBUb3BDb2RlciBTUk0gJm5kYXNoOyA1IGFuZCBzbyBvbi48XC9wPlxyXG5cclxuPHA+THVja2lseSB5b3UgaGF2ZSBhbHJlYWR5IHByZXBhcmVkIE0gZGlmZmVyZW50IHByb2JsZW1zLiBGb3IgZWFjaCBwcm9ibGVtIHlvdSBoYXZlIGRldGVybWluZWQgYSBzZXQgb2YgY29udGVzdHMgeW91IGNhbiBnaXZlIHRoYXQgcHJvYmxlbSB0by4gQWxzbyB5b3Uga25vdyB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIHByb2JsZW1zIGZvciBlYWNoIGNvbnRlc3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZpbmQgb3V0IHRoZSBtYXhpbWFsIG51bWJlciBvZiBkaWZmZXJlbnQgY29udGVzdHMgZm9yIHdoaWNoIHlvdSBjYW4gc2ltdWx0YW5lb3VzbHkgY29tcG9zZSBjb21wbGV0ZSBwcm9ibGVtc2V0cyBmcm9tIHRoZSBnaXZlbiBzZXQgb2YgcHJvYmxlbXMuIEFsbCBwcm9ibGVtcyBpbiB0aGUgcHJvYmxlbXNldHMgbXVzdCBiZSB1bmlxdWUsIGkuZS4gbm8gcHJvYmxlbSBjYW4gYmUgdXNlZCB0d2ljZSBpbiBkaWZmZXJlbnQgcHJvYmxlbXNldHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgZmlsZSBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIDIgaW50ZWdlcnMgTiBhbmQgTSAoMSAmbGU7IE4gJmxlOyAxNSwgMCAmbGU7IE0gJmxlOyA1MCkgJm5kYXNoOyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBjb250ZXN0cyBhbmQgdGhlIG51bWJlciBvZiBwcmVwYXJlZCBwcm9ibGVtcy4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdGhlIG5hbWUgb2YgY29udGVzdCwgZm9sbG93ZWQgYnkgdGhlIHJlcXVpcmVkIG51bWJlciBvZiBwcm9ibGVtcyBmb3IgdGhhdCBjb250ZXN0LiBUaGUgbmFtZSBvZiBhIGNvbnRlc3QgY29uc2lzdHMgb2YgbG93ZXItIGFuZCB1cHBlcmNhc2UgTGF0aW4gbGV0dGVycyBhbmRcL29yIGRpZ2l0cywgaXMgbm90IGVtcHR5IGFuZCBkb2VzIG5vdCBleGNlZWQgMTAwIGNoYXJhY3RlcnMuIENvbnRlc3QgbmFtZXMgYXJlIGNhc2Utc2Vuc2l0aXZlLiBJdCYjMzk7cyBndWFyYW50ZWVkIHRoYXQgYWxsIGNvbnRlc3QgbmFtZXMgd2lsbCBiZSBwYWlyd2lzZSBkaWZmZXJlbnQuIFRoZSByZXF1aXJlZCBudW1iZXIgb2YgcHJvYmxlbXMgZG9lcyBub3QgZXhjZWVkIDEwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgYSAocG9zc2libHkgZW1wdHkpIGxpc3Qgb2YgYWNjZXB0YWJsZSBjb250ZXN0IG5hbWVzIGZvciBlYWNoIHByb2JsZW0sIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gSXQmIzM5O3MgZ3VhcmFudGVlZCB0aGF0IGFsbCBjb250ZXN0IG5hbWVzIHdpbGwgYmUgY29ycmVjdCAoaS5lLiwgbm90ZWQgaW4gdGhlIHByZXZpb3VzIHNlY3Rpb24gb2YgdGhlIGN1cnJlbnQgdGVzdCBjYXNlKSBhbmQgdW5pcXVlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbGluZSBjb250YWluaW5nIHR3byB6ZXJvZXMgaW5kaWNhdGVzIHRoZSBlbmQgb2YgdGhlIGlucHV0IGZpbGUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIHByaW50IGFuIGFuc3dlciBmb3IgdGhhdCBjYXNlIG9uIGEgbmV3IGxpbmUsIGFzIHNob3duIGluIHRoZSBzYW1wbGUgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d