Lift

Problem Statement

Given two integers, N and M. N represents the number of requests, and M represents the number of lifts in a building. Your task is to optimize the allocation of lifts by minimizing the maximum request waiting time.

There are the following rules of lift allocation.

1. Lifts need to be given indices. i.e., choose lifts #1, #2, #3, etc. before anything else.
2. Since all N requests are known a priori, choose the Lift's initial location (at time t = 0) in a way that will help reduce waiting times.
3. The waiting lifts cannot be moved towards the target floor until the request is issued, even if all of the N requests' times are known a priori, except the starting time, or t = 0.
4. Even if a lift is in motion when a request for an optimality computation is made, it can still be considered.
5. If more than one Lift is available to fulfill the request at any given time while maintaining the same waiting time, use the Lift with the lower index. In other words, choose Lift #2 over Lift #4 if both can complete a task in 2 seconds.
6. Ignore how long it takes to enter and exit a lift.
7. A lift would not pause while fulfilling a request once it had begun. Once at the requested location, it would stop.
8. The Lift travels one floor per second.

Input

• N and M, two integers on the first line, represent the building's total number of requests and lifts, respectively.
• The following N lines contain three integers, T, S, and D, which stand for the request's timestamp, source floor, and destination floor.

Output

Display a single integer indicating the waiting time.

Constraints

0 <= T <= 86400.

0 <= S, D <= 100.

1 <= N, M <= 1000.

Examples

Input

3 2
0 2 3
4 2 5
6 7 3

Output

3

Explanation

There are two lifts and three requests.

Both lifts, lift #1 and lift #2, will initially be on floor 2 at t = 0. (Initial allocation).

Requests #1 and #2 can be answered immediately. Therefore there is no waiting period.

At time t = 1, level 3 will see the unallocated lift #1.

If necessary, Lift #1 can only move when the subsequent request is received at t = 4. Connect this to Rule #3 from the problem description.

At time t = (4 + 3) = 7, the lift #2 at floor 5 will become unallocated.

Since Lift #1 is currently at Floor #3 and will take 4 seconds to travel to Floor #7, the waiting time for Response Request #3 would be 4 seconds.

In this case, the total waiting time is 0, 0, 4, and the maximum waiting time is 4.

Instead, the waiting time would be calculated if Lift #2 was used to address Request #3.

At time t = 7, lift #2 will become unallocated, allowing us to wait 7-6 = 1 second for lift #2 to finish its prior request.

From floor five to floor seven, it will take 2 seconds for Lift #2 to get there. Total waiting time, therefore, equals 1 plus 2 or 3 seconds.

In this case, the waiting times for all requests are 0, 0, and 3, with 3 being the maximum waiting time.

Since the maximum waiting time must be kept to a minimum and Option 2 results in a shorter waiting time than Option 1, Option 2 is the best choice.

Therefore, the result is 3.

Input

5 3
0 2 3
4 2 5
6 7 3
3 5 6
2 5 7

Output

1

Explanation

There are 3 lifts and 5 requests.

Initially, at time t = 0, lifts #1 and #2 will be on floors 2 and 5, respectively (Initial allocation).

Requests #1, #4, and #5 can all be answered immediately. Thus there is no waiting period.

At time t = 1, level 3 will see the unallocated lift #1.

At floor 7, lift #2 will become available at time t = 2 + 2 = 4.

At time t = 3 + 1 = 4, the lift #3 at floor 6 will become unallocated.

Lift #1 can handle Request #2. 2 - 1 = 1 would be the waiting time.

Now, at time t = 4 + 1 + 3 = 8, lift #1 will become available at floor #5 once again.

Since request #3 will be on level #6 at t = 4, lift #3 can accommodate it. The waiting time is zero.

All requests have been waiting for 0, 1, 0, 0, and 0.

Therefore, the result is 1.
 

Note: Try to solve it yourself before moving on to the solution.

Must Read TCS CodeVita