#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int m;
int ans;
pair<int,int>ar[500005];
int dp[5010][5010];
int sfmx[500005];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>ar[i].second>>ar[i].first;
}
sort(ar+1,ar+n+1);
sfmx[n]=-ar[n].first*2+ar[n].second;
for(int i=n-1;i>=1;i--){
sfmx[i]=max(sfmx[i+1],ar[i].second-ar[i].first*2);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=-1e15;
}
}
int ans=-1e16;
dp[1][1]=ar[1].first*2+ar[1].second;
ans=dp[1][m-1]+sfmx[2];
for(int i=2;i<=n-1;i++){
dp[i][1]=max(dp[i-1][1],ar[i].first*2+ar[i].second);
for(int j=2;j<=m-1;j++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+ar[i].second);
}
ans=max(ans,dp[i][m-1]+sfmx[i+1]);
for(int j=3;j<=i;j++){
if(dp[i][j]-dp[i][j-1]>dp[i][j-1]-dp[i][j-2]){return 0;}
}
}
cout<<ans<<endl;
}
