#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;
}