Canadian Informatics Workshop: 2025 Day 1, Problem 1

Alex is a new student at Consec University, and she needs to choose which courses to take. She has ~N~ courses to choose from. The lectures for the ~i~-th course happen daily from day ~s_i~ to day ~f_i~ (inclusive), beginning at time ~b_i~ and ending at time ~e_i~ (inclusive), where lecture times are given in minutes from the start of the school day.

Alex must attend all the lectures—if two courses have overlapping lectures, she can't take both of them. Also, some courses are mandatory for graduating and must be taken. Additionally, Alex must take a minimum of ~M~ courses to be able to graduate.

Alex assigns a value ~v_i~ to each minute of a course to indicate her desire to take that course. The more worthwhile Alex considers one minute of a course to be, the larger the value of ~v_i~ she assigns to it. Help Alex maximize the total value of the courses she chooses!

Input Specification

The first line will contain two space-separated integers ~N~ and ~M~ (~1 \le N, M \le 20~).

The next ~N~ lines will each contain six space-separated integers ~s_i~, ~f_i~, ~b_i~, ~e_i~, ~m_i~, and ~v_i~ (~1 \le s_i \le f_i \le 1\,000~, ~1 \le b_i \le e_i \le 1\,000~, ~1 \le v_i \le 1\,000~, ~m_i \in \{0, 1\}~). If ~m_i = 0~, the ~i~-th course is optional, and if ~m_i = 1~, the ~i~-th course is mandatory.

The following table shows how the available 25 marks are distributed:

Marks Awarded	Bounds on ~N~	Additional Constraints
2 marks	~1\leq N\leq 2~	None
3 marks	~1\leq N\leq 20~	For all ~i~, ~m_i = 1~
5 marks	~1\leq N\leq 20~	For all ~i~, ~s_i = f_i~
10 marks	~1\leq N\leq 15~	None
5 marks	~1\leq N\leq 20~	None

Output Specification

If Alex cannot graduate because not all mandatory courses can be taken and/or not enough courses in total can be taken, then output -1.

Otherwise, output one integer, the maximum total value of the courses that Alex can fit into her schedule.

Sample Input

5 1
1 4 1 50 0 4
1 3 61 150 0 5
1 2 31 60 1 7
2 2 41 50 0 3
1 3 61 150 0 2

Sample Output

1770

Explanation for Sample Output

Since course 3 is mandatory, it must be taken. Course 3 conflicts with courses 1 and 4, so these courses cannot be taken. Courses 2 and 5 do not conflict with course 3, but they do conflict with each other, so only one of courses 2 and 5 can be taken. Courses 2 and 5 have the same total lecture time but course 2 has a greater total value, so it is better to take course 2 than course 5.

By taking the second and third courses, the total value of all courses is ~3 \times 90 \times 5 + 2 \times 30 \times 7 = 1\,770~.