K-th Largest Profit Plan for Honeymoon Room Bookings

The hotel manager receives all honeymoon room booking requests for the next year. Each booking request contains three pieces of information: the arrival date, the departure date, and the customer identity.

Since the hotel has only one honeymoon room, it can accommodate at most one newlywed couple at any given time. Two booking requests conflict if their stays overlap (note that check‐in and check‐out are fixed at 12:00 noon, so if one guest departs at the same time another arrives, they do not conflict).

Any booking that does not conflict with any other will inevitably be accepted because it benefits both the hotel and the customer. However, when conflicts occur, the hotel manager must reject some requests to maintain order – in any overlapping time slot, at most one booking can be accepted (and it is even allowed to reject all to avoid disputes).

The manager’s decision affects the total revenue (profit) obtained from the accepted bookings. For each booking, assume its profit is equal to the length of stay, i.e. the number of nights, computed as \(\text{departure} - \text{arrival}\). The overall plan’s profit is the sum of profits of the accepted bookings.

In making his decision, rather than choosing the plan with the maximum possible profit, a marketing consultant suggests a compromise: choose the plan with the k-th highest distinct total profit. Note that if several plans yield the same total profit, they are considered to have the same ranking. For example, if there are 3 plans with profit 3 and 2 plans with profit 2, then all plans with profit 3 are ranked first and those with profit 2 are ranked second.

Your task is to help the manager by selecting the k-th largest distinct profit among all valid (non-overlapping) booking schemes. If there is no such k-th profit, output -1.

Input Format: The first line contains two integers: \(n\) (the number of booking requests) and \(k\). Each of the following \(n\) lines contains the details of a booking: the arrival date, the departure date (both as integers), and the customer identity (a string). You may assume that a booking's profit is \(\text{departure} - \text{arrival}\>.

Note: Two bookings do not conflict if one’s departure time is exactly equal to the other’s arrival time.

inputFormat

The input begins with two integers \(n\) and \(k\) (number of bookings and the required ranking). Each of the next \(n\) lines contains an integer arrival date, an integer departure date, and a string representing customer identity, separated by spaces.

outputFormat

Output a single integer: the total profit of the k-th largest distinct valid booking scheme. If there are fewer than k distinct profit values, output -1.

sample

3 1
1 3 A
2 4 B
5 6 C

3