#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e5+6;
const ll INF=2e15;
struct event
{
ll pos;
bool f;
};
struct tower
{
ll l,r;
ll s,pos;
bool operator<(tower const& other)const
{
if(s-r!=other.s-other.r)return s-r<other.s-other.r;
else return pos<other.pos;
}
}t[MAXN];
///change cmp functions then do "xd"
bool cmpl(tower t1,tower t2)
{
if(t1.s-t1.r!=t2.s-t2.r)return t1.s-t1.r<t2.s-t2.r;
return t1.pos<t2.pos;
}
bool cmpr(tower t1,tower t2)
{
if(t1.s+t1.l!=t2.s+t2.l)return t1.s+t1.l<t2.s+t2.l;
return t1.pos<t2.pos;
}
bool cmpm(tower t1,tower t2)
{
if(t1.s!=t2.s)return t1.s<t2.s;
return t1.pos<t2.pos;
}
string status[MAXN];
set<tower,decltype(cmpl)*>LeftActive(cmpl);
set<tower,decltype(cmpr)*>RightActive(cmpr);
set<tower,decltype(cmpm)*>MiddleActive(cmpm);
set<tower,decltype(cmpl)*>LeftUnactive(cmpl);
set<tower,decltype(cmpr)*>RightUnactive(cmpr);
set<tower,decltype(cmpm)*>MiddleUnactive(cmpm);
map<ll,vector<event> >sweep_line;
int main()
{
ll n,k;
cin>>n>>k;
for(ll i=1;i<=n;i++)
{
ll x,p,s;
cin>>x>>p>>s;
t[i].l=x-p;
t[i].r=x+p;
t[i].s=s;
t[i].pos=i;
if(!sweep_line.count(x))
{
sweep_line[x]={};
}
sweep_line[t[i].l].push_back({i,1});
sweep_line[t[i].r].push_back({i,0});
RightUnactive.insert(t[i]);
status[i]="RU";
}
ll total_win=0,ans=-INF,last=-INF;
for(ll i=1;i<=n;i++)total_win+=t[i].s;
for(auto line:sweep_line)
{
total_win-=(LeftActive.size()-RightActive.size())*(line.first-last);
//cout<<line.first<<":\n";
vector<tower>v0,v1;
for(auto l:line.second)
{
if(l.f==0)v0.push_back(t[l.pos]);
else v1.push_back(t[l.pos]);
}
//cout<<"*1*\n";
for(auto v:v1)
{
if(status[v.pos]=="RU")
{
RightUnactive.erase(t[v.pos]);
MiddleUnactive.insert(t[v.pos]);
status[v.pos]="MU";
}
else if(status[v.pos]=="RA")
{
RightActive.erase(t[v.pos]);
MiddleActive.insert(t[v.pos]);
status[v.pos]="MA";
}
}
//cout<<"*2*\n";
for(auto v:v0)
{
if(status[v.pos]=="MA")
{
MiddleActive.erase(t[v.pos]);
LeftActive.insert(t[v.pos]);
status[v.pos]="LA";
}
if(status[v.pos]=="MU")
{
MiddleUnactive.erase(t[v.pos]);
LeftUnactive.insert(t[v.pos]);
status[v.pos]="LU";
}
}
//cout<<"*3*\n";
while(LeftActive.size()+RightActive.size()+MiddleActive.size()<k)
{
//cout<<LeftActive.size()+RightActive.size()+MiddleActive.size()<<endl;
//cout<<"*"<<LeftUnactive.size()<<" "<<MiddleUnactive.size()<<" "<<RightUnactive.size()<<endl;
//cout<<total_win<<endl;
if(LeftUnactive.size()+MiddleUnactive.size()+RightUnactive.size()==0)break;
pair<pair<ll,tower>,string>leu;
leu={{INF,{0ll,0ll,0ll}},"no"};
ll cost;
if(LeftUnactive.size()!=0)
{
auto f=(*LeftUnactive.begin());
cost=f.s+line.first-f.r;
leu=min(leu,{{cost,f},"LU"});
}
if(MiddleUnactive.size()!=0)
{
auto f=(*MiddleUnactive.begin());
cost=f.s;
leu=min(leu,{{cost,f},"MU"});
}
if(RightUnactive.size()!=0)
{
auto f=(*RightUnactive.begin());
cost=f.s+f.l-line.first;
leu=min(leu,{{cost,f},"RU"});
}
//cout<<"^"<<leu.first.first<<endl;
total_win-=leu.first.first;
if(status[leu.first.second.pos]=="LU")
{
LeftUnactive.erase(leu.first.second);
LeftActive.insert(leu.first.second);
status[leu.first.second.pos]="LA";
}
else if(status[leu.first.second.pos]=="MU")
{
MiddleUnactive.erase(leu.first.second);
MiddleActive.insert(leu.first.second);
status[leu.first.second.pos]="MA";
}
else if(status[leu.first.second.pos]=="RU")
{
RightUnactive.erase(leu.first.second);
RightActive.insert(leu.first.second);
status[leu.first.second.pos]="RA";
}
}
//cout<<"*4*\n";
for(;;)
{
//cout<<LeftActive.size()+MiddleActive.size()+RightActive.size()<<" "<<k<<endl;
//cout<<LeftActive.size()<<" "<<LeftUnactive.size()<<" "<<MiddleActive.size()<<" "<<MiddleUnactive.size()<<" "<<RightActive.size()<<" "<<RightUnactive.size()<<endl;
pair<pair<ll,tower>,string>mea,leu;
mea={{(ll)-1,{0ll,0ll,0ll}},"no"};
leu={{INF,{0ll,0ll,0ll}},"no"};
ll cost;
if(LeftUnactive.size()!=0)
{
auto f=(*LeftUnactive.begin());
cost=f.s+line.first-f.r;
leu=min(leu,{{cost,f},"LU"});
}
if(MiddleUnactive.size()!=0)
{
auto f=(*MiddleUnactive.begin());
cost=f.s;
leu=min(leu,{{cost,f},"MU"});
}
if(RightUnactive.size()!=0)
{
auto f=(*RightUnactive.begin());
cost=f.s+f.l-line.first;
leu=min(leu,{{cost,f},"RU"});
}
if(LeftActive.size()!=0)
{
auto it=LeftActive.end();
it--;
auto f=(*it);
cost=f.s+line.first-f.r;
mea=max(mea,{{cost,f},"LA"});
}
if(MiddleActive.size()!=0)
{
auto it=MiddleActive.end();
it--;
auto f=(*it);
cost=f.s;
mea=max(mea,{{cost,f},"MA"});
}
if(RightActive.size()!=0)
{
auto it=RightActive.end();
it--;
auto f=(*it);
cost=f.s+f.l-line.first;
mea=max(mea,{{cost,f},"RA"});
}
//cout<<mea.first.first<<" "<<leu.first.first<<endl;
if(mea.first.first<=leu.first.first)
{
break;
}
total_win+=mea.first.first;
total_win-=leu.first.first;
if(status[leu.first.second.pos]=="LU")
{
LeftUnactive.erase(leu.first.second);
LeftActive.insert(leu.first.second);
status[leu.first.second.pos]="LA";
}
else if(status[leu.first.second.pos]=="MU")
{
MiddleUnactive.erase(leu.first.second);
MiddleActive.insert(leu.first.second);
status[leu.first.second.pos]="MA";
}
else if(status[leu.first.second.pos]=="RU")
{
RightUnactive.erase(leu.first.second);
RightActive.insert(leu.first.second);
status[leu.first.second.pos]="RA";
}
if(status[mea.first.second.pos]=="LA")
{
LeftActive.erase(mea.first.second);
LeftUnactive.insert(mea.first.second);
status[mea.first.second.pos]="LU";
}
else if(status[mea.first.second.pos]=="MA")
{
MiddleActive.erase(mea.first.second);
MiddleUnactive.insert(mea.first.second);
status[mea.first.second.pos]="MU";
}
else if(status[mea.first.second.pos]=="RA")
{
RightActive.erase(mea.first.second);
RightUnactive.insert(mea.first.second);
status[mea.first.second.pos]="RU";
}
}
//cout<<"*5*\n";
ans=max(ans,total_win);
//cout<<total_win<<endl;
last=line.first;
}
cout<<-ans<<endl;
return 0;
}
