BSSPC '22 P7 - Exec Team Applications

View as PDF

Submit solution


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

Author:
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 ith applicant has an amiability of Ai and a bothersomeness Bi. 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?

Constraints

1N106

1MN

1Ai,Bi109

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 ith of these lines contains Ai and Bi.

Output Specification

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

Sample Input

Copy
3 2
1 3
3 2
4 1

Sample Output

Copy
1

Explanation

Selecting second and third applicants for the exec team, we get a quality of min(A2,A3)max(B2,B3)=min(3,4)max(2,1)=32=1. It can be shown that this is the maximum possible quality.


Comments

There are no comments at the moment.