Under construction

Still being built. Things may change

Friday Free Timetable

Time limit3sMemory limit512 MB

Summary
Count the subsets of classes with no Friday meetings, no overlapping classes on the same weekday, and total credits exactly k.
Level

Medium4 of 10

Topics
Bit manipulation, Brute force, Recursion
Solved
No attempts yet

Problem

Yun Heon is building his timetable for course registration season. Last semester he took a Friday class, and his friends teased him endlessly for it. This semester he has resolved to keep Friday free no matter what!!

You are given the weekday, start period, and end period of nn classes available at Korea University. Weekdays ww run from Monday to Friday and are given as integers 1 to 5. Start period ss and end period ee are integers from 11 to 1010. A class is worth e−s+1e-s+1 credits.

Yun Heon wants to take exactly kk credits this semester. He wants to know how many timetables leave Friday with no classes.

Two classes that meet on the same weekday and overlap in any period cannot both be taken. For example, a class from period 5 to period 7 on Tuesday and a class from period 7 to period 9 on Tuesday cannot be taken together.

Count the timetables that total exactly kk credits and have no classes on Friday for Yun Heon.

Input

The first line contains the number of available classes nn and the number of credits kk Yun Heon wants, separated by a space.

The next ii-th line contains the weekday wiw_i, start period sis_i, and end period eie_i of class ii, separated by spaces.

Output

Print the number of timetables that total exactly kk credits and have no classes on Friday.

Constraints

  • 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

Hint

A class that meets on Tuesday from period 5 to period 7 is given as 2 5 7.

Examples1

  1. Example 1

    Input
    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
    Expected output
    1