#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
int a, b;
int sp[9]= {};
scanf("%d %d", &n, &k);
vector<pair<int, int> > puhaha;
for(int i=1; i<=n; i++)
{
scanf("%d %d", &a, &b);
sp[b]++;
puhaha.push_back(make_pair(a, b));
}
sort(puhaha.begin(), puhaha.end());
int start=0, End=0;
int arr[9]= {};
int dist;
int boo;
int las;
int ans=0;
while(1)
{
if(start==n&&End==n)
break;
boo=1;
int cnt=0;
int p=1;
for(int i=1; i<=8; i++)
{
if(arr[i]==0)
continue;
cnt++;
if(p==1)
{
las=arr[i];
p=0;
}
else
{
if(las!=arr[i])
boo=0;
break;
}
}
if(boo==1)
{
if(End<n)
{
printf("%d %d %d %d\n", ans, arr[1], arr[2], las);
arr[puhaha[End].second]++;
if(cnt>=k)
ans=max(ans, puhaha[End].first-puhaha[start].first);
End++;
}
else
{
start++;
}
}
else
{
arr[puhaha[start].second]--;
start++;
}
}
printf("%d", ans);
}
//1 2 3 4 5 6 7 8 9 100
//1 2 3 1 1 2 3 1 1