#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <unordered_set>
using namespace std;

long long ans, dp[110000], dp1[110000], f[210000], ind[210000];
int tmp[2100000], n, k, len;
int len1;
int son[11000000][2], s[11000000];
long long ss[11000000];
int root[210000], root1[210000];

struct aa {
    int a, b;
} a[110000];

bool cmp(aa a, aa b) {
    return a.a + a.b < b.a + b.b;
}

pair<int, long long> operator + (pair<int, long long> x, pair<int, long long> y) {
    return make_pair(x.first + y.first, x.second + y.second);
}

pair<int, long long> operator - (pair<int, long long> x, pair<int, long long> y) {
    return make_pair(x.first - y.first, x.second - y.second);
}

pair<int, long long> query(int k, int q, int h, int l, int r) {
    if (!k)
        return make_pair(0, 0);
    else if (l <= q && h <= r)
        return make_pair(s[k], ss[k]);
    else if (r <= ((q + h) >> 1))
        return query(son[k][0], q, (q + h) >> 1, l, r);
    else if (((q + h) >> 1) < l)
        return query(son[k][1], ((q + h) >> 1) + 1, h, l, r);
    else return query(son[k][0], q, (q + h) >> 1, l, r) + query(son[k][1], ((q + h) >> 1) + 1, h, l, r);
}

long long calc(int pre, int p) {
    long long sum = dp[pre];
    int q = 0, h = n + 1, mid;
    while (q < h - 1) {
        mid = (q + h) / 2;
        if (a[mid].a + a[mid].b <= 2 * tmp[p])
            q = mid;
        else
            h = mid; 
    }
    if (q <= pre)
        return sum;
    else {
        pair<int, long long> xx = query(root[q], -1e9, 1e9, -1e9, tmp[p]) - query(root[pre], -1e9, 1e9, -1e9, tmp[p]);
        return sum + 1LL * tmp[p] * xx.first - xx.second;
    }
    return sum;
}

long long calc1(int pre, int p) {
    long long sum = f[pre];
    int q = -1, h = n + 1, mid;
    while (q < h - 1) {
        mid = (q + h) >> 1;
        if (a[mid].a + a[mid].b > 2 * tmp[p])
            h = mid;
        else
            q = mid; 
    }
    if (h > p)
        return sum;
    else {
        pair <int, long long> xx = query(root1[p], -1e9, 1e9, tmp[pre], 1e9) - query(root1[h - 1], -1e9, 1e9, tmp[pre], 1e9);
        return sum - 1LL * tmp[pre] * xx.first + xx.second;
    }
    return sum;
}

void ins(int &k, int k1, int l, int r, int x) {
    if (!k) {
        k = ++len1;
        s[k] = s[k1];
        ss[k] = ss[k1];
     }
    s[k] += 1;
    ss[k] += x;
    if (l < r) {
        if (x <= ((l + r) >> 1))
            ins(son[k][0], son[k1][0], l, (l + r) >> 1, x), son[k][1] = son[k1][1];
        else
            ins(son[k][1], son[k1][1], ((l + r) >> 1) + 1, r, x), son[k][0] = son[k1][0];
    }
}

void doit(int l, int r, int q, int h) {
    int mid = (l + r) / 2;
    f[mid] = 1e18;
    int ind = q;
    for (int i = q; i <= h; i++) {
        long long tmp = calc(i, mid);
        if (tmp < f[mid])
            f[mid] = tmp, ind = i;
    }
    if (l < mid)
        doit(l, mid - 1, q, ind);
    if (mid < r)
        doit(mid + 1, r, ind, h);
}

void doit1(int l, int r, int q, int h) {
    int mid = (l + r) / 2;
    dp1[mid] = 1e18;
    int ind = q;
    for (int i = q; i <= h; i++) {
        long long tmp = calc1(i, mid);
        if (tmp < dp1[mid])
            dp1[mid] = tmp, ind = i;
    }
    if (l < mid)
        doit1(l, mid - 1, q, ind);
    if (mid < r)
        doit1(mid + 1, r, ind, h);
}


int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].a, &a[i].b);
        if (a[i].a > a[i].b)
            swap(a[i].a, a[i].b);
        ans += a[i].b - a[i].a;
        tmp[++len] = a[i].a;
        tmp[++len] = a[i].b;
    }
    sort(a + 1, a + n + 1, cmp);
    sort(tmp + 1, tmp + len + 1);
    for (int i = 1; i <= n; i++)
        ins(root[i], root[i - 1], -1e9, 1e9, a[i].b);
    for (int i = 1; i <= n; i++)
        ins(root1[i], root1[i - 1], -1e9, 1e9, a[i].a);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        dp[i] = 1e18;
    for (int i = 1; i <= k; i++) {
        doit(1, len, 0, n);
        doit1(1, n, 1, len);
        memcpy(dp, dp1, sizeof dp);
        
    }
    printf("%lld\n", ans + 2 * dp[n]);
}