The computer club execs team has received
execs applications, out of which they will select a team of
execs for next year.
Each of the
applicants bring positive and negative traits to the club; specifically, the
applicant has an amiability of
and a bothersomeness
.
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
execs, selected among the
applicants?
Constraints



Subtask 1 [40%]

Subtask 2 [60%]
No additional constraints.
Input Specification
The first line contains two integers,
and
.
The next
lines contain two integers each, where the
of these lines contains
and
.
Output Specification
Output a single integer, the maximum possible quality of a team of
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
.
It can be shown that this is the maximum possible quality.
Comments