BSSPC '22 P7 - Exec Team Applications

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Python 5.0s
Memory limit: 256M

Problem type

The computer club execs team has received N execs applications, out of which they will select a team of M execs for next year.

Each of the N applicants bring positive and negative traits to the club; specifically, the i^\text{th} applicant has an amiability of A_i and a bothersomeness B_i. A chain is only as strong as its weakest link, so the quality of an exec team is the minimum amiability of its members, minus the maximum bothersomeness of its members.

Of course, the current execs want to choose the best possible team for next year. They want to know, what is the maximum quality of a team of M execs, selected among the N applicants?


1 \le N \le 10^6

1 \le M \le N

1 \le A_i, B_i \le 10^9

Subtask 1 [40%]

M = 2

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains two integers, N and M.

The next N lines contain two integers each, where the i^{th} of these lines contains A_i and B_i.

Output Specification

Output a single integer, the maximum possible quality of a team of M executives.

Sample Input

3 2
1 3
3 2
4 1

Sample Output



Selecting second and third applicants for the exec team, we get a quality of \min(A_2, A_3) - \max(B_2, B_3) = \min(3, 4) - \max(2, 1) = 3 - 2 = 1. It can be shown that this is the maximum possible quality.


There are no comments at the moment.