#include <bits/stdc++.h>
using namespace std;
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
const long long BIG = 1000000000000000000LL;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
void solve();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
typedef pair<int, ll> pil;
const int borne = 200*1005;
int nbPerles, nbVoulu;
struct Perle
{
int couleur, taille, relCoul;
};
Perle perles[borne];
ll rep = -BIG;
// Début segtree
int posInSegtree[4*borne];
int stNbOn[4*borne];
ll stSom[4*borne];
int cl = 0, cr = -1;
void addElem(int posOp, int val, int coeff)
{
int cur = posInSegtree[posOp];
stNbOn[cur] += coeff;
stSom[cur] += (ll)(coeff*val);
while (cur > 1) {
cur /= 2;
stNbOn[cur] = stNbOn[2*cur] + stNbOn[2*cur+1];
stSom[cur] = stSom[2*cur] + stSom[2*cur+1];
}
}
void init(int nod, int leftNod, int rightNod)
{
if (leftNod == rightNod) {
posInSegtree[leftNod] = nod;
} else {
int midNod = (leftNod + rightNod) / 2;
init(2*nod, leftNod, midNod);
init(2*nod+1, midNod+1, rightNod);
}
}
int opWalk = 0;
pil walk(int nod, int nbPrendre)
{
opWalk++;
if (stNbOn[nod] == 0 || nbPrendre == 0) {
//cout << nod << " " << endl << flush;
return {0,0};
}
if (stNbOn[nod] <= nbPrendre) {
return {stNbOn[nod], stSom[nod]};
}
pil ret = walk(2*nod+1, nbPrendre); // D'abord marcher vers la droite
//assert(ret.fi <= nbPrendre);
nbPrendre -= ret.fi;
pil oth = walk(2*nod, nbPrendre); // ensuite compléter avec la gauche
//assert(oth.fi <= nbPrendre);
ret.fi += oth.fi;
ret.se += oth.se;
return ret;
}
void upd(int iPerle, int coeff)
{
addElem(perles[iPerle].relCoul, perles[iPerle].couleur, coeff);
}
int opSt = 0;
void ajusterSegtree(int newLeft, int newRight)
{
while (cl > newLeft) { // Ajout
--cl; ++opSt;
upd(cl, 1);
}
while (cr < newRight) { // Ajout
++cr; ++opSt;
upd(cr, 1);
}
while (cl < newLeft) { // Suppression
upd(cl, -1);
++cl; ++opSt;
}
while (cr > newRight) { // Suppresion
upd(cr, -1);
--cr; ++opSt;
}
////assert(stNbOn[1] == cr-cl+1);
}
void calcDp(int caLeft, int caRight, int optLeft, int optRight)
{
//cout << "## " << caLeft << " " << caRight << " " << optLeft << " " << optRight << endl << flush;
if (caLeft > caRight) return;
int caMid = min((caLeft + caRight) / 2, optRight-nbVoulu+1);
if (caMid < caLeft) return;
int debOpt = max(caMid+nbVoulu-1, optLeft);
chmax(optRight, debOpt);
ll sousRep = -BIG;
int bestOpt = debOpt;
form2(optTry, debOpt, optRight+1) {
ajusterSegtree(caMid, optTry);
pil ret = walk(1, nbVoulu);
//cout << "###\n";
//assert(ret.fi <= nbVoulu);
if (ret.fi == nbVoulu) {
ll nvRep = ret.se - 2*(perles[optTry].taille - perles[caMid].taille);
//cout << caMid << " " << optTry << " : " << ret.fi << " " << ret.se << " -> " << nvRep << "\n";
if (optTry == debOpt || nvRep > sousRep) {
sousRep = nvRep;
bestOpt = optTry;
}
}
}
chmax(rep, sousRep);
calcDp(caLeft, caMid-1, optLeft, bestOpt);
calcDp(caMid+1, caRight, bestOpt, optRight);
}
void solve()
{
cin >> nbPerles >> nbVoulu;
form(i, nbPerles) { cin >> perles[i].couleur >> perles[i].taille; }
// Tri par couleur
sort(perles, perles+nbPerles, [&] (Perle a, Perle b) { return tie(a.couleur, a.taille) < tie(b.couleur, b.taille); });
// Détermine les relCoul
form(i, nbPerles) perles[i].relCoul = i;
// Tri par taille
sort(perles, perles+nbPerles, [&] (Perle a, Perle b) { return tie(a.taille, a.couleur) < tie(b.taille, b.couleur); });
//form(i, nbPerles) cout << i << ") " << perles[i].couleur << " " << perles[i].taille << "\n";
init(1, 0, nbPerles-1);
calcDp(0, nbPerles-1, 0, nbPerles-1);
cout << rep << "\n";
}
