9 2
1 1
5 1
6 1
9 1
100 1
2 2
7 2
3 3
8 3

6

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }
	return x * f;
}

#define maxn 100010
#define oo 2147483647

struct Cow {
	int x, b;
	Cow() {}
	Cow(int _, int __): x(_), b(__) {}
	bool operator < (const Cow& t) const { return x < t.x; }
} cs[maxn];
int n, K;

#define MOD 2097151
bool Equal(int a[8], int b[8]) {
	for(int i = 0; i < 8; i++) if(a[i] != b[i]) return 0;
	return 1;
}
int CNT;
struct Hash {
	int ToT, head[MOD+1], nxt[maxn], more[maxn][8], val[maxn];
	
	void init() {
		for(int t = 1; t <= ToT; t++) {
			int u = 0;
			for(int i = 0; i < 8; i++) CNT++, u = u ^ more[t][i] & MOD;
			head[u] = 0;
		}
		ToT = 0;
		return ;
	}
	
	int Find(int tmp[8]) {
		int u = 0;
		for(int i = 0; i < 8; i++) u = u ^ tmp[i] & MOD;
		for(int e = head[u]; e; e = nxt[e]) if(Equal(more[e], tmp)) return val[e];
		return oo;
	}
	void Insert(int tmp[8], int v) {
		int u = 0;
		for(int i = 0; i < 8; i++) u = u ^ tmp[i] & MOD;
		val[++ToT] = v; for(int i = 0; i < 8; i++) more[ToT][i] = tmp[i]; nxt[ToT] = head[u]; head[u] = ToT;
		return ;
	}
} hh;

int lstb[maxn][8], more[maxn][8], ans = -1;
void work(int S) {
	int lCNT = CNT;
	memset(more, 0, sizeof(more));
	int cnt[8], mb;
	for(int i = 0; i < 8; i++) if(S >> i & 1){ mb = i; break; }
	bool has = 0;
	for(int i = 1; i <= n;) {
		while(i <= n && !(S >> cs[i].b & 1)) i++;
		if(i > n) break;
		
		memset(cnt, 0, sizeof(cnt));
		hh.init(); hh.Insert(cnt, i - 1);
		int l = i, r = i;
		while(r <= n && (S >> cs[r].b & 1)) {
			cnt[cs[r].b]++;
			for(int j = 0; j < 8; j++) {
				if(S >> j & 1) more[r][j] = cnt[j] - cnt[mb];
				CNT++;
			}
			if(hh.Find(more[r]) == oo) hh.Insert(more[r], r);
			r++;
		}
		r--;
		for(int p = l; p <= r; p++) {
			int pre = hh.Find(more[p]) + 1; bool ok = 1;
			for(int j = 0; j < 8; j++) {
				CNT++;
				if((S >> j & 1) && lstb[p][j] < pre){ ok = 0; break; }
			}
			if(ok) has = 1, ans = max(ans, cs[p].x - cs[pre].x);
		}
		i = r + 1;
	}
//	printf("work(%d) %d %d\n", S, CNT, CNT - lCNT);
	return ;
}

int main() {
	n = read(); K = read();
	for(int i = 1; i <= n; i++) {
		int x = read(), b = read() - 1;
		cs[i] = Cow(x, b);
	}
	
	sort(cs + 1, cs + n + 1);
	int lst[8]; memset(lst, 0, sizeof(lst));
	for(int i = 1; i <= n; i++) {
		lst[cs[i].b] = i;
		for(int j = 0; j < 8; j++) lstb[i][j] = lst[j];
	}
	int all = (1 << 8) - 1;
	for(int S = 0; S <= all; S++) {
		int cnt = 0;
		for(int i = 0; i < 8; i++) cnt += S >> i & 1;
		if(cnt >= K) work(S);
	}
	
	printf("%d\n", ans);
	
	return 0;
}