프로그래밍 대회

프로그래밍 대회는 대회마다 나오는 문제의 유형이 다르다. 예를 들어, 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 두 개가 주어진다.

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