#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)1e5+10;
int n, m;
array<int,2> a[mxN];
int32_t main()
{
cin >> n >> m; int ans = -1e18;
for(int i = 0; i < n; i++) cin >> a[i][1] >> a[i][0];
sort(a,a+n); int sum = 0;
for(int i = 0; i < n; i++){
priority_queue<int,vector<int>,greater<int>> pq =
priority_queue<int,vector<int>,greater<int>>(); sum = 0;
for(int j = i+1; j < n; j++){
int cost = a[i][1]+a[j][1]-2*(a[j][0]-a[i][0]);
if(sz(pq)==m-2) ans = max(ans, sum+cost);
pq.push(a[j][1]); sum+=a[j][1];
if(sz(pq)>m-2) sum-=pq.top(), pq.pop();
}
}
cout << ans << "\n";
}
