아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

금공강 사수

면접 대비

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

요약
정확히 k학점이 되고 금요일 수업이 없으며 같은 요일에서 시간이 겹치지 않는 수업 조합의 수를 센다.
난이도

보통10점 중 5점

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

문제

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

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

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

이때, 같은 요일, 같은 교시에 열리는 두 수업은 동시에 수강할 수 없다. 예를 들어, 화요일 55교시부터 77교시까지 열리는 수업과 화요일 77교시부터 99교시까지 열리는 수업은 동시에 수강할 수 없다.

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

입력

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

다음 ii번째 줄에는 ii번 수업의 요일, 시작 교시, 끝 교시 w_i,s_i,e_iw\_i, s\_i, e\_i가 공백으로 구분되어 주어진다.

출력

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

제한

  • 1≤n≤201 \le n \le 20
  • 1≤k≤221 \le k \le 22
  • 1≤w_i≤51 \le w\_i \le 5
  • 1≤s_i≤e_i≤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