#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<ll> V(n), C(n), V_(n), C_(n);

    for (int i = 0; i < n; ++i) {
        cin >> V[i] >> C[i];
        C[i] *= 2;
    }

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return C[i] < C[j];
    });

    V_ = V, C_ = C;

    for (int i = 0; i < n; ++i) {
        C[i] = C_[ord[i]];
        V[i] = V_[ord[i]];
    }

    auto solve = [&](ll penalty) { // siuuuuu
        pair<ll, int> ans{-3e18, -1};
        pair<ll, int> dp{-3e18, -1};

        for (int i = 0; i < n; ++i) {
            pair<ll, int> now = {dp.first + V[i] - C[i] - penalty, dp.second - 1};
            ans = max(ans, now);
            now = {dp.first + V[i] - penalty, dp.second - 1};
            dp = max({dp, pair{V[i] + C[i] - penalty, -1}, now});
        }

        return pair{ans.first, -ans.second};
    };

    ll lo = -3e12, hi = 3e12;

    while (lo + 1 < hi) {
        ll mid = (lo + hi) / 2;
        auto [dp, mink] = solve(mid);
        if (mink <= k) {
            hi = mid;
        } else {
            lo = mid;
        }
    }


    auto [dp, mink] = solve(hi);

    cout << dp + k * hi << '\n';

    return 0;
}