만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

금공강 사수

시간 제한3초메모리 제한512 MB

요약
금요일 수업이 없고 같은 요일에 시간이 겹치지 않으며 총 학점이 정확히 k인 수업 조합의 개수를 구합니다.
난이도

보통10점 중 4점

유형
비트 연산, 완전 탐색, 재귀
정답자
아직 제출이 없습니다

문제

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

고려대학교에서 수강할 수 있는 nn개의 수업마다 요일, 시작 교시, 끝 교시가 주어진다. 요일 ww는 월요일부터 금요일까지 1부터 5까지의 정수로 주어진다. 시작 교시 ss와 끝 교시 ee는 11부터 1010까지의 정수이다. 수업의 학점은 e−s+1e-s+1이다.

윤헌이는 이번 학기에 정확히 kk 학점을 듣고 싶다. 금요일에 수업이 없는 시간표가 몇 가지인지 알고 싶다.

같은 요일에 열리고 교시가 하나라도 겹치는 두 수업은 함께 수강할 수 없다. 예를 들어, 화요일 55교시부터 77교시까지 열리는 수업과 화요일 77교시부터 99교시까지 열리는 수업은 함께 들을 수 없다.

정확히 kk 학점이면서 금요일에 수업이 하나도 없는 윤헌이의 시간표 가짓수를 구하시오.

입력

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

다음 ii번째 줄에는 ii번 수업의 요일 wiw_i, 시작 교시 sis_i, 끝 교시 eie_i가 공백으로 구분되어 주어진다.

출력

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

제한

  • 1≤n≤201 \le n \le 20
  • 1≤k≤221 \le k \le 22
  • 1≤wi≤51 \le w_i \le 5
  • 1≤si≤ei≤101 \le s_i \le e_i \le 10

힌트

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

예제1

  1. 예제 1

    입력
    10 15
3 4 4
3 4 9
3 6 8
1 10 10
3 2 5
2 6 10
5 5 5
2 5 7
3 6 10
3 1 6
    예상 출력
    1