题解：P1712 [NOI2016] 区间

	while (true)
	{
		// w[1] < m means there is no node that is covered >= m 
		// 我喜欢装 X，别管上面的
		// 就是没有一个点被覆盖的次数 >= m 即 当前还不符合要求 
		while (w[1] < m && r <= n) r++, update(1, 1, cur, Interval[a[r].id].ft, Interval[a[r].id].sd, 1); // 不符合要求 且 没出界，覆盖次数 + 1 
		if (w[1] < m) break; // 都遍历完所有的了，还没有公共点就 break 
		while (w[1] >= m && l <= n) l++, update(1, 1, cur, Interval[a[l].id].ft, Interval[a[l].id].sd, -1); // 符合要求 且 没出界，覆盖次数 - 1 
		ans = min(ans, a[r].len - a[l].len); // 更新答案 
	}

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
	ll res = 0, f = 1; char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 5e5 + 5;
struct Point { // 离散化数组 
	int x, id;
} p[N << 1];
bool cmp1(Point x, Point y) { return x.x < y.x; } // 从小到大排序 
struct node { // 线段数组 
	int len, id;
} a[N];
bool cmp2(node x, node y) { return x.len < y.len; } // 按线段长度排序 
pii Interval[N]; // 存离散化过后的线段左右端点 

#define ls (u << 1)
#define rs (u << 1 | 1)
#define Mid ((L + R) >> 1)

int w[N << 3], lazy[N << 3]; // 线段树 
// 要开 8 倍的原因是要存线段两个端点 
void pushup(int u) { w[u] = max(w[ls], w[rs]); } // pushup 取 max 
void pushdown(int u)
{
	if (lazy[u])
	{
		w[ls] += lazy[u], w[rs] += lazy[u];
		lazy[ls] += lazy[u], lazy[rs] += lazy[u];
		lazy[u] = 0;
	}
}
void update(int u, int L, int R, int l, int r, int k)
{
	if (l == 0 && r == 0) return ; // 防止【奶龙】情况 
	if (l <= L && R <= r)
	{
		lazy[u] += k;
		w[u] += k;
		return ;
	}
	pushdown(u);
	if (l <= Mid) update(ls, L, Mid, l, r, k);
	if (r > Mid) update(rs, Mid + 1, R, l, r, k);
	pushup(u);
}
int main()
{
	int n = read(), m = read();
	for (int i = 1; i <= n; i++)
	{
		int l = read(), r = read();
		a[i] = {r - l, i};
		p[2 * i - 1] = {l, i};
		p[2 * i] = {r, i};
	}
	sort(p + 1, p + 2 * n + 1, cmp1);
	sort(a + 1, a + n + 1, cmp2);
	p[0].x = -INF;
	int cur = 0;
	for (int i = 1; i <= 2 * n; i++)
	{
		cur += (p[i].x != p[i - 1].x); // 如果当前不等于上一个，就 + 1 
		if (!Interval[p[i].id].ft) Interval[p[i].id].ft = cur; // 当前 id 第一次 
		else Interval[p[i].id].sd = cur; // 当前 id 第二次 
	}
	int ans = INF, l = 0, r = 0;
	while (true)
	{
		// w[1] < m
		// 就是没有一个点被覆盖的次数 >= m 即 当前还不符合要求 
		while (w[1] < m && r <= n) r++, update(1, 1, cur, Interval[a[r].id].ft, Interval[a[r].id].sd, 1); // 不符合要求 且 没出界，覆盖次数 + 1 
		if (w[1] < m) break; // 都遍历完所有的了，还没有公共点就 break 
		while (w[1] >= m && l <= n) l++, update(1, 1, cur, Interval[a[l].id].ft, Interval[a[l].id].sd, -1); // 符合要求 且 没出界，覆盖次数 - 1 
		ans = min(ans, a[r].len - a[l].len); // 更新答案 
	}
	write(ans == INF ? -1 : ans);
	return 0;
}