#include <cstdio>
#include <algorithm>
using namespace std;
struct node {
    int l, r;
} x[100010];
bool cmp(node a, node b) {
    if (a.l == b.l) {
        return a.r > b.r;
    }
    return a.l < b.l;
}
int n, k;
int l[100010], r[100010], d[100010];
int dp[100010][110][2];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x[i].l, &x[i].r);
    }
    sort(x + 1, x + n + 1, cmp);
    int m = 0;
    int nowr = 0, nowl = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        if (x[i].l > nowr) {
            ans += nowr - nowl;
            nowl = x[i].l;
            nowr = x[i].r;
            x[++m] = x[i];
        } else if (x[i].r > nowr) {
            nowr = x[i].r;
            x[++m] = x[i];
        } else {
            k--;
        }
    }
    ans += nowr - nowl;
    if (k <= 0) {
        printf("%lld\n", ans);
        return 0;
    }
    for (int i = 1; i <= m; i++) {
        l[i] = x[i].l;
        r[i] = x[i].r;
    }
    for (int i = 1; i < m; i++) {
        if (x[i + 1].l > x[i].r) continue;
        int rightpos = upper_bound(l + 1, l + m + 1, x[i].r) - l - 1;
        d[i]++;
        d[rightpos]--;
    }
    n = 0;
    for (int i = 1; i <= m; i++) {
        d[i] += d[i - 1];
        if (d[i]) {
            k--;
        } else {
            x[++n] = x[i];
        }
    }
    if (k <= 0) {
        printf("%lld\n", ans);
        return 0;
    }
    for (int i = 0; i <= k; i++) {
        dp[0][i][0] = dp[0][i][1] = 1e9;
    }
    dp[0][0][0] = 0;
    x[n + 1].l = 1e9;
    x[n + 1].r = 1e9;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1]);
            dp[i][j][1] = 1e9;
            if (j != 0) {
                dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][1] + min(x[i].r, x[i + 1].l) - x[i].l);
                dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][0] + min(x[i].r, x[i + 1].l) - max(x[i].l, x[i - 1].r));
            }
        }
    }
    printf("%d\n", ans - min(dp[n][k][0], dp[n][k][1]));
    return 0;
}