과외 선생님
시간 제한8초메모리 제한512 MB
각 학생이 필요한 수업 횟수와 가능한 요일이 주어질 때, 한 학생당 하루에 최대 한 번 수업을 하면서 W주 안에 모든 수업을 마칠 수 있는지 판정한다.
문제
당신은 과외 선생님으로 일한다. 많은 학생에게 수업을 하다 보니 시험 기간에는 특히 바쁘다. 이번 시험 기간도 예외가 아니다.
각 학생이 수업을 들을 수 있는 요일과 그 학생에게 해야 할 수업 횟수를 알고 있다. 하루에는 한 학생에게만 수업을 할 수 있다. 시험이 끝날 때까지 남은 주 수는 정해져 있다. 모든 수업을 끝낼 수 있을까?
입력
입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.
N W
t1 c1
list-of-days-of-the-week
t2 c2
list-of-days-of-the-week
...
tN cN
list-of-days-of-the-week
데이터 세트의 첫 줄에는 두 정수 N (0 < N ≤ 100)과 W (0 < W ≤ 1010)가 주어진다. N은 학생 수이고, W는 남은 주 수이다. 다음 2N개 줄에 학생 정보가 주어진다. 각 학생의 정보는 두 줄로 주어진다. 첫 줄에는 두 정수 ti와 ci가 주어진다. ti (0 < ti ≤ 1010)는 i번째 학생이 필요한 수업 횟수이고, ci (0 < ci ≤ 7)는 i번째 학생이 수업을 들을 수 있는 요일 수이다. 둘째 줄에는 ci개의 요일 목록(일요일, 월요일, 화요일, 수요일, 목요일, 금요일, 토요일)이 주어진다.
입력의 끝은 두 개의 0이 있는 줄로 표시한다. 이 줄은 처리하지 않는다.
출력
각 데이터 세트에 대해 모든 수업을 끝낼 수 있으면 “Yes”를, 아니면 “No”를 출력한다.