#include <bits/stdc++.h>

using namespace std;

constexpr int64_t INF = 1e18;

void chmax(int64_t &x, int64_t v) {
    x = max(x, v);
}

signed main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int S, N;
    cin >> S >> N;

    vector<pair<int,int>> people(S);
    for (auto &[H, A]: people) {
        cin >> A >> H;
    }
    sort(people.begin(), people.end());

    int64_t ans = -INF;
    vector<int64_t> dp(N + 1, -INF);
    for (auto [H, A]: people) {
        auto ndp = dp;
        for (int j = N - 1; j >= 1; j--) {
            chmax(ndp[j + 1], dp[j] + A);
        }
        chmax(ndp[1], A + H);
        dp = ndp;
        chmax(ans, dp[N] - H);
    }
    cout << ans << '\n';
}