#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
constexpr int MAX = 1000007;
int n, k_range, range_check;
struct rangeof
{
int p, k;
int nr;
void read(int i)
{
cin >> p >> k;
nr = i;
}
};
rangeof tabp[MAX];
int maximum = 0;
bool sort_by_first(const rangeof & z1, const rangeof & z2)
{
if (z1.p < z2.p)
return true;
else if (z1.p == z2.p && z1.k > z2.k)
return true;
return false;
}
struct range {
int p, k;
};
bool visited[MAX];
int range(const rangeof & z)
{
return z.k - z.p;
}
bool reached_k = false;
void do_odd1(rangeof z1, int i, int k)
{
rangeof pom;
while (++i <= n && ++k <= k_range)
{
if (z1.k <= tabp[i].p)
return;
pom.p = max(z1.p, tabp[i].p);
pom.k = min(z1.k, tabp[i].k);
int dl = range(pom);
if (reached_k && dl <= maximum)
{
--k;
continue;
}
if (k == k_range) {
if (!reached_k)
reached_k = true;
if (dl > maximum)
maximum = dl;
--k;
continue;
}
do_odd1(pom, i, k);
--k;
}
}
void do_main()
{
for (int i = 1; i <= range_check; ++i)
{
if (!visited[i])
{
do_odd1(tabp[i], i, 1);
}
}
}
int main()
{
std::ios_base::sync_with_stdio(0);
cin >> n >> k_range;
range_check = n - k_range - 1;
for (int i = 1; i <= n; ++i) {
tabp[i].read(i);
}
std::sort(tabp + 1, tabp + n + 1, sort_by_first);
do_main();
cout << maximum << endl;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8cXVldWU+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3RleHByIGludCBNQVggPSAxMDAwMDA3OwppbnQgbiwga19yYW5nZSwgcmFuZ2VfY2hlY2s7CgpzdHJ1Y3QgcmFuZ2VvZgp7CiAgICBpbnQgcCwgazsKICAgIGludCBucjsKCiAgICB2b2lkIHJlYWQoaW50IGkpCiAgICB7CiAgICAgICAgY2luID4+IHAgPj4gazsKICAgICAgICBuciA9IGk7CiAgICB9Cn07CgpyYW5nZW9mIHRhYnBbTUFYXTsgCgppbnQgbWF4aW11bSA9IDA7Cgpib29sIHNvcnRfYnlfZmlyc3QoY29uc3QgcmFuZ2VvZiAmIHoxLCBjb25zdCByYW5nZW9mICYgejIpCnsKICAgIGlmICh6MS5wIDwgejIucCkKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIGVsc2UgaWYgKHoxLnAgPT0gejIucCAmJiB6MS5rID4gejIuaykKICAgICAgICByZXR1cm4gdHJ1ZTsKCiAgICByZXR1cm4gZmFsc2U7Cn0KCnN0cnVjdCByYW5nZSB7CiAgICBpbnQgcCwgazsKfTsKCmJvb2wgdmlzaXRlZFtNQVhdOwoKaW50IHJhbmdlKGNvbnN0IHJhbmdlb2YgJiB6KQp7CiAgICByZXR1cm4gei5rIC0gei5wOwp9Cgpib29sIHJlYWNoZWRfayA9IGZhbHNlOwoKdm9pZCBkb19vZGQxKHJhbmdlb2YgejEsIGludCBpLCBpbnQgaykKewogICAgcmFuZ2VvZiBwb207CgogICAgd2hpbGUgKCsraSA8PSBuICYmICsrayA8PSBrX3JhbmdlKQogICAgewogICAgICAgIGlmICh6MS5rIDw9IHRhYnBbaV0ucCkKICAgICAgICAgICAgcmV0dXJuOwoKICAgICAgICBwb20ucCA9IG1heCh6MS5wLCB0YWJwW2ldLnApOwogICAgICAgIHBvbS5rID0gbWluKHoxLmssIHRhYnBbaV0uayk7CgogICAgICAgIGludCBkbCA9IHJhbmdlKHBvbSk7CgogICAgICAgIGlmIChyZWFjaGVkX2sgJiYgZGwgPD0gbWF4aW11bSkKICAgICAgICB7CiAgICAgICAgICAgIC0tazsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQoKICAgICAgICBpZiAoayA9PSBrX3JhbmdlKSB7CiAgICAgICAgICAgIGlmICghcmVhY2hlZF9rKQogICAgICAgICAgICAgICAgcmVhY2hlZF9rID0gdHJ1ZTsKICAgICAgICAgICAgaWYgKGRsID4gbWF4aW11bSkKICAgICAgICAgICAgICAgIG1heGltdW0gPSBkbDsKICAgICAgICAgICAgLS1rOwogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICB9CgogICAgICAgIGRvX29kZDEocG9tLCBpLCBrKTsKICAgICAgICAtLWs7CiAgICB9Cn0KCnZvaWQgZG9fbWFpbigpCnsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IHJhbmdlX2NoZWNrOyArK2kpCiAgICB7CiAgICAgICAgaWYgKCF2aXNpdGVkW2ldKQogICAgICAgIHsKICAgICAgICAgICAgZG9fb2RkMSh0YWJwW2ldLCBpLCAxKTsKICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKCkKewogICAgc3RkOjppb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwoKICAgIGNpbiA+PiBuID4+IGtfcmFuZ2U7CgogICAgcmFuZ2VfY2hlY2sgPSBuIC0ga19yYW5nZSAtIDE7CgogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CiAgICAgICAgdGFicFtpXS5yZWFkKGkpOwogICAgfQoKICAgIHN0ZDo6c29ydCh0YWJwICsgMSwgdGFicCArIG4gKyAxLCBzb3J0X2J5X2ZpcnN0KTsKCiAgICBkb19tYWluKCk7CgogICAgY291dCA8PCBtYXhpbXVtIDw8IGVuZGw7Cn0=