#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 101;

ll 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];
    }

    ll ans = -3e18;

    for (int s = 0; s < n; ++s) {
        for (int x = 0; x < n; ++x) {
            fill(dp[x], dp[x] + n, -3e18);
        }
        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] - abs(C[i] - C[p]));
//                    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] - abs(C[i] - C[s]));
//            ans = max(ans, dp[i][k] + 2 * min(C[i], C[s]));
        }
    }

    cout << ans << '\n';

    return 0;
}