#include <iostream>
#include <fstream>
#define N 1005
using namespace std;
ifstream fin("cursuri.in");
ofstream fout("cursuri.out");
///cu problema specctacolelor = sort dupa of
struct curs
{
    int oi, of;
    bool p;
}a[N];
int n, cer, k;

void Sort()
{
  ///bubble sort
  int i,m=n;
  bool ord=0;
  while(!ord)
  {
      ord=1;
      for(i=1;i<m;i++)
        if(a[i].of>a[i+1].of)
      {
          ord=0;
          swap(a[i], a[i+1]);
      }
      m--;
  }
}
void Citire()
{
    fin>>cer>>n>>k;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i].oi>>a[i].of;
        a[i].p=0;
    }
}
int  Cerinta1()
{
    int cate=0,i,j;
    curs sal[N];
    for(i=0;i<=k;i++)sal[i].oi=sal[i].of=0;
    ///Greedy
    for(i=1;i<=n;i++)
    {
        int p=0;
        for(j=1;j<=k;j++)
            if(a[i].oi>=sal[j].of &&a[i].oi-sal[j].of<=a[i].oi-sal[p].of)
            p=j;
        if(p)
            sal[p]=a[i], cate++;
    }
    return cate;
}

bool Test(int x)
{
    int i;
    for(i=1;i<=n;i++)
        a[i].of=a[i].oi+x, a[i].p=0;
    Sort();
    if(Cerinta1()==n)return 1;
    else return 0;
}
int  cerinta2()
{
    int dmax=0,i,gasit=1;
    ///durata maxima
    for(i=1;i<=n;i++)
        if(a[i].of-a[i].oi>dmax)
         dmax=a[i].of-a[i].oi;
    ///cautare binara
    int st=1, dr=dmax,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(Test(mij))
            gasit=mij, st=mij+1;
        else dr=mij-1;
    }
    return gasit;
}
int main()
{
  Citire();
  Sort();
  if(cer==1) fout<<Cerinta1();
  else fout<<cerinta2();
  return 0;
}