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?

Constraints

~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

1

Explanation

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.