#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    return out << "(" << a.x << ", " << a.y << ")";
}

template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
    out << "[";
    forn(i, sz(v)) {
        if(i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

mt19937 rnd(time(NULL));

const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = INF + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

const int N = 100 * 1000 + 13;

int n, k;
pt a[N];

bool read () {
    if (scanf("%d%d", &n, &k) != 2)
        return false;
    forn(i, n)
        scanf("%d%d", &a[i].x, &a[i].y);
    return true;
}

int t[4 * N];
li f[N];

void upd(int x, int val){
    for (int i = x; i < N; i |= i + 1)
        f[i] += val;
}

li get(int x){
    li res = 0;
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
        res += f[i];
    return res;
}

void build(int v, int l, int r){
    if (l == r - 1){
        t[v] = 1;
        return;
    }

    int m = (l + r) / 2;

    build(v * 2, l, m);
    build(v * 2 + 1, m, r);

    t[v] = t[v * 2] + t[v * 2 + 1];
}

void upd(int v, int l, int r, int pos){
    if (l == r - 1){
        --t[v];
        return;
    }

    int m = (l + r) / 2;

    if (pos < m)
        upd(v * 2, l, m, pos);
    else
        upd(v * 2 + 1, m, r, pos);

    t[v] = t[v * 2] + t[v * 2 + 1];
}

li get(int v, int l, int r, int tot){
    if (l == r - 1)
        return get(l);

    int m = (l + r) / 2;

    if (tot - t[v * 2] <= 0)
        return get(v * 2, l, m, tot);
    else
        return get(v * 2 + 1, m, r, tot - t[v * 2]);
}

int pos[N];

void solve() {
    sort(a, a + n);

    build(1, 0, n);
    memset(f, 0, sizeof(f));

    vector<pt> nums;
    forn(i, n) nums.pb(mp(a[i].x + a[i].y, i));
    sort(all(nums));
    forn(i, n) pos[nums[i].y] = i;

    forn(i, n) upd(pos[i], a[i].x + a[i].y);

    set<pt, greater<pt>> l;
    li sum = 0;
    li ans = INF64;

    forn(i, n){
        int j = i;
        int x = a[i].x;

        upd(pos[i], -a[i].y - a[i].x);
        upd(1, 0, n, pos[i]);

        l.insert(mp(a[i].y - a[i].x, i));
        sum += a[i].y - a[i].x;

        while (j + 1 < n && a[j + 1].x == a[i].x){
            ++j;

            upd(pos[j], -a[j].y - a[j].x);
            upd(1, 0, n, pos[j]);

            l.insert(mp(a[j].y - a[j].x, j));
            sum += a[j].y - a[j].x;
        }

        while (sz(l) > k){
            sum -= l.begin()->x;
            l.erase(l.begin());
        }

        while (!l.empty() && t[1] + sz(l) > k){
            li sum1 = sum + get(1, 0, n, k - sz(l)) + li(x) * (sz(l) - (k - sz(l)));
            li sum2 = sum - l.begin()->x + get(1, 0, n, k - sz(l) + 1) + li(x) * ((sz(l) - 1) - (k - sz(l) + 1));

            if (sum2 > sum1)
                break;

            sum -= l.begin()->x;
            l.erase(l.begin());
        }

        if (sz(l) + t[1] >= k)
            ans = min(ans, sum + get(1, 0, n, k - sz(l)) + li(x) * (sz(l) - (k - sz(l))));

        i = j;
    }

    printf("%lld\n", ans);
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    int tt = clock();

#endif

    cerr.precision(15);
    cout.precision(15);
    cerr << fixed;
    cout << fixed;

#ifdef _DEBUG
    while(read()) {
#else
    if(read()) {
#endif
        solve();

#ifdef _DEBUG
    cerr << "TIME = " << clock() - tt << endl;
    tt = clock();
#endif

    }
}