31837번 - 시간표 만들기

문제

찬솔이는 이번 학기에 22학점을 들을 계획이다. 시간표를 만들기 위해 찬솔이는 다음과 같이 들을 예정인 과목들을 그룹으로 정리했다.

• 그룹 A : [전공종합설계1(가), 전공종합설계2(나), 컴퓨터공학특강1]
• 그룹 B : [네트워크프로그래밍(가), 네트워크프로그래밍(나)]
• 그룹 C : [멀티미디어응용]
• 그룹 D : [SW융합세미나1, 정보기술세미나1]
• 그룹 E : [파일처리(가), 파일처리(나)]
• 그룹 F : [디지털공학(나), 디지털공학(다)]
• 그룹 G : [문제해결]
• 그룹 H : [프로그래밍언어(가)]

그룹마다 그룹에 속한 강의 중 최대 하나의 강의를 선택해서 시간표를 구성한다. 각 강의에는 강의가 진행되는 요일, 강의 시작 시각, 강의 종료 시각이 있고, 선택한 강의끼리 진행 시간이 겹치면 안 된다. 요일이 다르거나 강의가 끝나는 동시에 다른 강의가 시작하는 것은 시간이 겹치는 것이 아니다.

꼭 모든 그룹에서 강의를 하나씩 선택해야 하는 것이 아니며, 하나의 그룹에 학점이 다른 강의가 있을 수도 있음에 유의하라. 또한, 모든 강의는 일주일에 한 번만 진행된다. 즉, 입력으로 주어지는 강의는 모두 서로 다른 강의이다.

찬솔이는 들을 예정인 과목들을 위와 같이 그룹으로 정리했을 때, 선택한 강의의 학점 합이 정확히 22가 되도록 시간표를 만들 수 있는 경우의 수가 궁금해졌다.

입력

첫째 줄에 그룹의 개수 $N$이 주어진다.

둘째 줄부터 $N$개의 그룹과 각 그룹에 포함된 과목의 정보가 주어진다. 그룹에 포함된 과목의 개수 $A_i$가 먼저 주어진다. 이어서 $A_i$개의 줄에 걸쳐 각 과목의 학점 수 $C,ドル 요일 $D,ドル 강의 시작 시각 $S,ドル 강의 종료 시각 $E$가 공백으로 구분되어 주어진다.

강의 시작 시각 $S$와 종료 시각 $E$는 HH시 MM분이 HH:MM 형식으로 주어진다.

출력

주어진 입력으로 조건을 만족하며 만들 수 있는 22학점 시간표의 개수를 출력한다.

제한

• 1ドル\le N\le 15$
• 1ドル\le A_i\le 15$
• $\sum_{i=1}^{N}A_i\le 15$
• 1ドル\le C\le 22$
• 1ドル\le D\le 7$
• 00 $\le$ HH $\le$ 23
• 00 $\le$ MM $\le$ 59
• $S<E,ドル 즉, 강의가 자정을 넘어서까지 진행되거나, 시작하자마자 종료하는 경우는 없다.
• 입력으로 주어지는 수는 모두 정수이다.

힌트