시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVhYzFjXHVjZDVjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMzAwXHVkNjhjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHVjNjQwIFx1ZDU2OFx1YWVkOCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1YzgxYyBcdWNkOWNcdWI4MjUgXHVkNjE1XHVjMmRkXHVjNzQ0IFx1Y2MzOFx1YWNlMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNzI3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUHJvYmxlbXNldHRpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkl0JiMzOTtzIHdlbGwta25vd24gdGhhdCBkaWZmZXJlbnQgcHJvZ3JhbW1pbmcgY29udGVzdHMgcmVxdWlyZSBkaWZmZXJlbnQga2luZCBvZiBwcm9ibGVtcy4gRm9yIGV4YW1wbGUsIG1heGltYWwgYXJyYXkgc2l6ZSBmb3IgVG9wQ29kZXIgcHJvYmxlbSBpcyBvbmx5IDUwLCBhbmQgeW91IGRlZmluaXRlbHkgY2FuIG5vdCBnaXZlIGEgU3VmZml4IFRyZWUgcHJvYmxlbSB0byBJT0kgYmVjYXVzZSBjaGlsZHJlbiB3aWxsIG5vdCBoYXZlIGEgY2hhbmNlIHRvIHNvbHZlIGl0IChleGNlcHQgb2Ygc29tZSB0b3VyaXN0aWMtaW5jbGluZWQgb25lcykuIFRodXMgbm90IGV2ZXJ5IHByb2JsZW0gaXMgYWNjZXB0YWJsZSBmb3IgZXZlcnkgY29udGVzdC48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBwcmVwYXJpbmcgcHJvYmxlbXNldHMgZm9yIE4gZGlmZmVyZW50IGNvbnRlc3RzLiBUaGVzZSBjb250ZXN0cyByZXF1aXJlIGRpZmZlcmVudCBudW1iZXIgb2YgcHJvYmxlbXMsIGRlcGVuZGluZyBvZiB0eXBlLiBGb3IgZXhhbXBsZSwgQUNNIElDUEMgc3R5bGUgcHJvYmxlbXNldCB1c3VhbGx5IGhhcyAxMCBwcm9ibGVtcywgVG9wQ29kZXIgU1JNICZuZGFzaDsgNSBhbmQgc28gb24uPFwvcD5cclxuXHJcbjxwPkx1Y2tpbHkgeW91IGhhdmUgYWxyZWFkeSBwcmVwYXJlZCBNIGRpZmZlcmVudCBwcm9ibGVtcy4gRm9yIGVhY2ggcHJvYmxlbSB5b3UgaGF2ZSBkZXRlcm1pbmVkIGEgc2V0IG9mIGNvbnRlc3RzIHlvdSBjYW4gZ2l2ZSB0aGF0IHByb2JsZW0gdG8uIEFsc28geW91IGtub3cgdGhlIHJlcXVpcmVkIG51bWJlciBvZiBwcm9ibGVtcyBmb3IgZWFjaCBjb250ZXN0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5GaW5kIG91dCB0aGUgbWF4aW1hbCBudW1iZXIgb2YgZGlmZmVyZW50IGNvbnRlc3RzIGZvciB3aGljaCB5b3UgY2FuIHNpbXVsdGFuZW91c2x5IGNvbXBvc2UgY29tcGxldGUgcHJvYmxlbXNldHMgZnJvbSB0aGUgZ2l2ZW4gc2V0IG9mIHByb2JsZW1zLiBBbGwgcHJvYmxlbXMgaW4gdGhlIHByb2JsZW1zZXRzIG11c3QgYmUgdW5pcXVlLCBpLmUuIG5vIHByb2JsZW0gY2FuIGJlIHVzZWQgdHdpY2UgaW4gZGlmZmVyZW50IHByb2JsZW1zZXRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGZpbGUgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyAyIGludGVnZXJzIE4gYW5kIE0gKDEgJmxlOyBOICZsZTsgMTUsIDAgJmxlOyBNICZsZTsgNTApICZuZGFzaDsgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgY29udGVzdHMgYW5kIHRoZSBudW1iZXIgb2YgcHJlcGFyZWQgcHJvYmxlbXMuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHRoZSBuYW1lIG9mIGNvbnRlc3QsIGZvbGxvd2VkIGJ5IHRoZSByZXF1aXJlZCBudW1iZXIgb2YgcHJvYmxlbXMgZm9yIHRoYXQgY29udGVzdC4gVGhlIG5hbWUgb2YgYSBjb250ZXN0IGNvbnNpc3RzIG9mIGxvd2VyLSBhbmQgdXBwZXJjYXNlIExhdGluIGxldHRlcnMgYW5kXC9vciBkaWdpdHMsIGlzIG5vdCBlbXB0eSBhbmQgZG9lcyBub3QgZXhjZWVkIDEwMCBjaGFyYWN0ZXJzLiBDb250ZXN0IG5hbWVzIGFyZSBjYXNlLXNlbnNpdGl2ZS4gSXQmIzM5O3MgZ3VhcmFudGVlZCB0aGF0IGFsbCBjb250ZXN0IG5hbWVzIHdpbGwgYmUgcGFpcndpc2UgZGlmZmVyZW50LiBUaGUgcmVxdWlyZWQgbnVtYmVyIG9mIHByb2JsZW1zIGRvZXMgbm90IGV4Y2VlZCAxMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIGEgKHBvc3NpYmx5IGVtcHR5KSBsaXN0IG9mIGFjY2VwdGFibGUgY29udGVzdCBuYW1lcyBmb3IgZWFjaCBwcm9ibGVtLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIEl0JiMzOTtzIGd1YXJhbnRlZWQgdGhhdCBhbGwgY29udGVzdCBuYW1lcyB3aWxsIGJlIGNvcnJlY3QgKGkuZS4sIG5vdGVkIGluIHRoZSBwcmV2aW91cyBzZWN0aW9uIG9mIHRoZSBjdXJyZW50IHRlc3QgY2FzZSkgYW5kIHVuaXF1ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGxpbmUgY29udGFpbmluZyB0d28gemVyb2VzIGluZGljYXRlcyB0aGUgZW5kIG9mIHRoZSBpbnB1dCBmaWxlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCBhbiBhbnN3ZXIgZm9yIHRoYXQgY2FzZSBvbiBhIG5ldyBsaW5lLCBhcyBzaG93biBpbiB0aGUgc2FtcGxlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=