Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM ICPC 2018 World Finals
Language:
The Bonus Salary!
 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 2733 Accepted: 738

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.

• 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.

Sample Input

```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
```

Sample Output

`16`

Hint

The optimal strategy is: