The Bonus Salary!
Description
In order to encourage employees' productivity, ACM Company has made a new policy. At the beginning of a period, they give a list of tasks to each employee. In this list, each task is assigned a "productivity score". After the first K days, the employee who gets the highest score will be awarded bonus salary.
Due to the difficulty of tasks, for task i-th:
- It must be done from hh_Li : mm_Li : ss_Li to hh_Ri : mm_Ri : ss_Ri.
- This range of time is estimated very strictly so that anyone must use all of this time to finish the task.
Moreover, at a moment, each employee can only do at most one task. And as soon as he finishes a task, he can start doing another one immediately.
XYY is very hard-working. Unfortunately, he's never got the award. Thus, he asks you for some optimal strategy. That means, with a given list of tasks, which tasks he should do in the first K days to maximize the total productivity score. Notice that one task can be done at most once.
Input
The first line contains 2 integers N and K (1 ≤ N ≤ 2000, 0 ≤ K ≤ 100), indicating the number of tasks and days respectively. This is followed by N lines; each line has the following format:
hh_Li:mm_Li:ss_Li hh_Ri:mm_Ri:ss_Ri w
Which means, the i-th task must be done from hh_Li : mm_Li : ss_Li to hh_Ri : mm_Ri : ss_Ri and its productivity score is w. (0 ≤hh_Li, hh_Ri ≤ 23, 0 ≤mm_Li, mm_Ri, ss_Li, ss_Ri ≤ 59, 1 ≤ w ≤ 10000). We use exactly 2 digits (possibly with a leading zero) to represent hh, mm and ss. It is guaranteed that the moment hh_Ri : mm_Ri : ss_Ri is strictly later than hh_Li : mm_Li : ss_Li.
Output
The output only contains a nonnegative integer --- the maximum total productivity score.
5 2
09:00:00 09:30:00 2
09:40:00 10:00:00 3
09:29:00 09:59:00 10
09:30:00 23:59:59 4
07:00:00 09:31:00 3
16Hint
The optimal strategy is:
Day1: Task1, Task 4
Day2: Task 3
The total productivity score is 2 + 4 + 10 = 16.