27375번 - 금공강 사수

문제

윤헌이는 수강신청 시즌이 되어 시간표를 짜고 있다. 지난 학기 금요일에 수업을 들어 친구들에게 온갖 놀림을 받은 윤헌이는 이번 학기에는 꼭 금요일 공강을 지켜내기로 결심했다!!

고려대학교에서 수강할 수 있는 $n$개의 수업의 요일과 시작 교시, 끝 교시가 주어진다. 요일 $w$는 월요일부터 금요일까지 각각 1부터 5까지의 정수로 주어지며, 수업의 시작 교시 $s,ドル 끝 교시 $e$가 1ドル$부터 10ドル$까지의 정수로 주어진다. 수업의 학점은 $e-s+1$이다.

이번 학기에 $k$ 학점을 듣고 싶은 윤헌이는 금요일에 공강이 있는 시간표의 가짓수가 궁금하다.

이때, 같은 요일, 같은 교시에 열리는 두 수업은 동시에 수강할 수 없다. 예를 들어, 화요일 5ドル$교시부터 7ドル$교시까지 열리는 수업과 화요일 7ドル$교시부터 9ドル$교시까지 열리는 수업은 동시에 수강할 수 없다.

윤헌이를 위해 정확히 $k$ 학점을 들으면서 금요일에 수업이 하나도 없는 시간표의 가짓수를 구해 보자!

입력

첫 줄에 수강 가능한 수업의 개수 $n$과 윤헌이가 듣고 싶은 학점 $k$가 공백으로 구분되어 주어진다.

다음 $i$번째 줄에는 $i$번 수업의 요일, 시작 교시, 끝 교시 $w_i, s_i, e_i$가 공백으로 구분되어 주어진다.

출력

정확히 $k$ 학점을 들으면서 금요일에 수업이 하나도 없는 시간표의 가짓수를 출력한다.

제한

• 1ドル \le n \le 20$
• 1ドル \le k \le 22$
• 1ドル \le w_i \le 5$
• 1ドル \le s_i \le e_i \le 10$

노트

화요일 5ドル$교시부터 7ドル$교시까지 열리는 수업은 2 5 7과 같이 주어진다.