#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 101;

ll V[N], C[N], V_[N], C_[N];
ll dp[N][N];

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

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

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

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

    memcpy(V_, V, sizeof(V));
    memcpy(C_, C, sizeof(C));

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

    ll ans = -3e18;

    for (int s = 0; s < n; ++s) {
        memset(dp, -0x3f, sizeof(dp));
        dp[s][1] = V[s];

        for (int i = s + 1; i < n; ++i) {
            for (int p = s; p < i; ++p) {
                for (int m = 1; m < k; ++m) {
                    dp[i][m + 1] = max(dp[i][m + 1], dp[p][m] + V[i] + 2 * min(C[i], C[p]));
                }
            }
            ans = max(ans, dp[i][k] + 2 * min(C[i], C[s]));
        }
    }

    cout << ans << '\n';

    return 0;
}