프로그래밍 대회

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

우현이는 서로 다른 $N$개의 프로그래밍 대회에 문제를 출제한다. 대회마다 필요한 문제 수는 서로 다르다. 예를 들어 ACM-ICPC 형식의 대회는 보통 10문제가, TopCoder SRM은 5문제가 필요하다.

우현이는 미리 $M$개의 문제를 준비해 두었고, 각 문제를 어떤 대회에 낼 수 있는지도 정해 두었다.

모든 대회를 동시에 개최한다고 할 때, 최대 몇 개의 대회를 실제로 열 수 있는지 구하여라. 대회를 열려면 그 대회에 필요한 문제 수를 모두 채워야 하고, 한 문제는 최대 한 대회에만 사용할 수 있다.

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

각 테스트 케이스의 첫 줄에는 대회의 수 $N$과 준비한 문제의 수 $M$이 주어진다 ($1 \le N \le 15$, $0 \le M \le 50$).

이어지는 $N$개의 줄에는 각 대회의 이름과 그 대회를 열기 위해 필요한 문제 수가 주어진다. 대회 이름은 알파벳 대소문자와 숫자로 이루어지고 길이는 100자를 넘지 않으며, 대소문자를 구분한다. 필요한 문제 수는 100 이하이다.

그다음 $M$개의 줄에는 각 문제를 낼 수 있는 대회의 이름이 공백으로 구분되어 주어진다. 어떤 문제를 낼 수 있는 대회가 하나도 없으면 그 줄은 비어 있다.

입력의 마지막 줄에는 0이 두 개 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 동시에 개최할 수 있는 대회의 최대 개수를 케이스 번호와 함께 한 줄에 출력한다. $k$번째 테스트 케이스의 답이 $c$이면 Case #k: c 형식으로 출력한다.