#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
//=======================*
ifstream fin("intervale3.in");
ofstream fout("intervale3.out");
//=======================*
int n, m, i, j, k, ok, minim, i2, j2, nr;
int maxim, x, y, z, o, ii, jj, i1, j1, p, sum;
//int a[1001][1001], b[1001][1001];
int v[100001], w[100001], r[100001];
//int d[3][1000001], e[3][1000001];
//=======================*
int main(){
    fin >> n >> m;
    for(i = 1; i <= n; i ++)
        fin >> v[i] >> w[i];
    for(i = 1; i < n; i ++)
        for(j = i + 1; j <= n; j ++){
            if(w[i] > w[j]){
                k = v[i];
                v[i] = v[j];
                v[j] = k;
                k = w[i];
                w[i] = w[j];
                w[j] = k;
            }
        }
    for(i = 1; i < n; i ++)
        r[i] = (v[i + 1] - w[i]) / 2 + (v[i + 1] - w[i]) % 2;
    x = r[1];
    nr = 1;
    minim = 2000000001;
    i = 1;
    sum = 2000000001;
    while(i < n){
        j = i + 1;
        while(r[i] >= r[j]){
            j ++;
        }
        j --;
        if(j - i + 1 >= m - 1){
            sum = r[j];
            for(o = j; o > j - m + 1; o --)
                if(sum < r[o] && j > 0)
                    sum = r[o];
        }
        if(sum < minim)
            minim = sum;
        i = j + 1;
    }
    fout << minim;
    return 0;
}