Longest Common Meeting Time

The law firm "Bajtazar 父子" has received an urgent case that requires a meeting with a group of lawyers. Each lawyer has a fixed free time interval during which they can attend a meeting. You are to choose exactly \( k \) lawyers so that the time slot during which all of the selected lawyers are free (i.e. the intersection of their free time intervals) is as long as possible.

Formally, each lawyer \( i \) is available during the time interval \( [L_i, R_i] \). If you choose a set \( S \) of \( k \) lawyers, the meeting can be held during the time interval \[ \left[\max_{i\in S}L_i,\; \min_{i\in S}R_i\right] \] with duration \( \max(0,\min_{i\in S}R_i-\max_{i\in S}L_i) \). Your task is to choose \( k \) lawyers to maximize this meeting duration.

Note: If the intersection of the chosen intervals is empty, the meeting duration is defined as 0.

inputFormat

The first line contains two integers \( n \) and \( k \) (\(1 \le k \le n\)). Each of the following \( n \) lines contains two integers \( L_i \) and \( R_i \) (with \( L_i \le R_i \)), representing the start and end times of the \( i \)-th lawyer's free interval.

outputFormat

Output a single integer, which is the maximum possible meeting duration (i.e., \(\max(0, \min_{i\in S}R_i - \max_{i\in S}L_i)\)) you can achieve by choosing exactly \( k \) lawyers.

sample

3 2
1 4
2 6
8 9

2