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_L_i : mm_L_i : ss_L_i to hh_R_i : mm_R_i : ss_R_i.
• 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.

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_L_i:mm_L_i:ss_L_i hh_R_i:mm_R_i:ss_R_i w

Which means, the i-th task must be done from hh_L_i : mm_L_i : ss_L_i to hh_R_i : mm_R_i : ss_R_i and its productivity score is w. (0 ≤hh_L_i, hh_R_i ≤ 23, 0 ≤mm_L_i, mm_R_i, ss_L_i, ss_R_i ≤ 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_R_i : mm_R_i : ss_R_i is strictly later than hh_L_i : mm_L_i : ss_L_i.　

The output only contains a nonnegative integer --- the maximum total productivity score.

The optimal strategy is:
Day1: Task1, Task 4
Day2: Task 3
The total productivity score is 2 + 4 + 10 = 16.