#include <bits/stdc++.h>
using ll = long long;
typedef std::pair<ll,ll> pll;
///Eu sei como resolver para um M infinito, mas como faco para um M FINITO???
///Ideia do M infinito:
///O custo do absoluto eh basicamente MAX*2 - MIN*2
///O resto N importa muito, eu tenho que pegar a soma dos M-2 maiores elementos entre L e R (alem da soma do A de L e R)
///Relaxacao lagrangiana talvez?
#define MAX 2005
int N,M;
std::vector<pll> vec;
bool existe[MAX][MAX];
ll tab[MAX][MAX];
ll inf = (1LL<<60LL);
ll dp(int pos,int pega){
if(pega==M){
return 0;
}
if(pos==N)return -inf;
if(existe[pos][pega])return tab[pos][pega];
existe[pos][pega]=true;
ll resp = -inf;
resp=std::max(resp,dp(pos+1,pega));
if(!pega){
resp=std::max(resp,dp(pos+1,pega+1)+(2LL*vec[pos].first)+vec[pos].second);
}else if(pega!=M-1){
resp=std::max(resp,dp(pos+1,pega+1)+vec[pos].second);
}else {
resp=std::max(resp,dp(pos+1,pega+1)+vec[pos].second-(2LL*vec[pos].first));
}
return tab[pos][pega]=resp;
}
int main()
{
std::cin>>N>>M;
for(int i=0;i!=N;++i){
ll a,b;
std::cin>>a>>b;
vec.push_back({b,a});
}
std::sort(vec.begin(),vec.end());
std::cout<<dp(0,0)<<"\n";
}
