33885번 - 마지막 수강신청

문제

도현이는 어느덧 졸업을 앞두고 마지막 학기 수강신청을 하고 있다. 도현이는 졸업하기 전 학교에서 마지막으로 수강하고 싶은 후보 과목 $N$개를 정리했다. 각 과목은 다음과 같은 정보를 가지고 있다:

• $c_i$: $i$번째 과목을 수강하여 얻을 수 있는 학점을 나타낸다.
• $s_i$: 매주 $i$번째 과목이 진행되는 강의 횟수를 나타낸다.
• $d_{i,j}$: 매주 $i$번째 과목의 $j$번째 강의가 열리는 요일을 나타낸다.
• $h_{i,j}$: 매주 $i$번째 과목의 $j$번째 강의가 열리는 시각을 나타낸다. 강의는 $h_{i,j}$시 정각에 시작해서 $h_{i,j}$시 59ドル$분에 종료된다.

도현이는 이 강의들의 일부만으로 시간표를 구성했을 때, 졸업 요건인 $M$학점을 수강할 수 있는지 알고 싶다. 수강하고자 하는 과목들 간 시간이 겹치지 않아야 하며, 이동시간 등은 고려하지 않는다.

입력

첫 번째 줄에 수강하고 싶은 후보 과목의 개수 $N,ドル 졸업을 위해 수강해야 하는 최소 학점 $M$이 공백으로 구분되어 주어진다. $(1 \leq N \leq 10;$ 1ドル\leq M \leq 24)$

두 번째 줄부터 $N$줄에 걸쳐 각각 후보 과목에 대한 정보가 주어진다. 각 줄에 $c_i,ドル $s_i,ドル $d_{i,1},h_{i,1}, ..., d_{i,s_i},h_{i,s_i}$ 가 공백으로 구분되어 주어진다. $(1\leq c_i \leq4;$ 1ドル\leq s_i \leq 3;$ 0ドル \leq h_{i,j} \leq 23;$ $d_{i,j}$ 는 MON, TUE, WED, THU, FRI중 하나의 값을 가진다.$)$

같은 과목의 강의 시간들은 오름차순으로 주어지며, 서로 다른 강의 시간이 겹치는 입력은 주어지지 않는다.

출력

후보 과목으로 시간표를 구성하여 $M$학점 이상 수강할 수 있다면 YES, 아니라면 NO를 출력한다.

제한

노트

요일의 순서는 MON $<$ TUE $<$ WED $<$ THU $<$ FRI로 정의되며, 각각 순서대로 월요일부터 금요일까지를 나타낸다.