#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1) << (x))
#define sz(x) (int)(x).size()
#define TIME_USED cerr << "\n Time lapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << "s \n";
template<class T1 , class T2>
bool maximize(T1 &a , T2 b){
if (a < b) return a = b , true; else return false;
}
template<class T1 , class T2>
bool minimize(T1 &a , T2 b){
if (a > b) return a = b , true; else return false;
}
template<class T>
void compress(vector<T>&data){
sort(data.begin() , data.end());
data.resize(unique(data.begin() , data.end()) - data.begin());
}
template<class T1 , class T2>
T2 Find(const vector<T1>&data , T2 y){
return upper_bound(data.begin() , data.end() , y) - data.begin();
}
const int N = (int) 1e5;
const LL inf = (LL) 1e18;
int n , k;
int x[N + 2] , p[N + 2] , s[N + 2];
namespace subtask1{
bool check(){
return n <= 15;
}
//... solveing_
struct Node{
int l , r;
bool operator < (const Node&other) {
if (l != other.l) return l < other.l;
return r < other.r;
}
};
LL calc(vector<Node>&data){
sort(data.begin() , data.end());
LL res = inf;
vector<int> nen , lef , rig;
for(int i = 0; i < data.size(); ++i){
nen.push_back(data[i].l) , nen.push_back(data[i].r);
lef.push_back(data[i].l) , rig.push_back(data[i].r);
}
compress(nen);
sort(lef.begin() , lef.end());
sort(rig.begin() , rig.end());
LL sum_lef = 0 , sum_rig = 0;
LL sl_lef = 0 , sl_rig = 0;
for(int i = 0; i < sz(lef); ++i){
++sl_lef;
sum_lef += lef[i];
}
for(int i = 0 , ptr_lef = 0 , ptr_rig = 0; i < sz(nen); ++i){
while (ptr_rig < sz(rig) && rig[ptr_rig] < nen[i]){
sum_rig += rig[ptr_rig];
++sl_rig;
++ptr_rig;
}
while (ptr_lef < sz(lef) && lef[ptr_lef] < nen[i]){
sum_lef -= lef[ptr_lef];
--sl_lef;
++ptr_lef;
}
LL cost = sl_rig * nen[i] - sum_rig + sum_lef - sl_lef * nen[i];
minimize(res , cost);
}
return res;
}
void main_code(){
LL ans = -inf;
for(int mask = 0; mask < MASK(n); ++mask){
vector<Node> v;
if (__builtin_popcount(mask) != k) continue;
LL tot = 0;
for(int i = 0; i < n; ++i){
if (BIT(mask , i)){
v.push_back({x[i + 1] - p[i + 1] , x[i + 1] + p[i + 1]});
}
else tot += s[i + 1] ;
}
tot -= calc(v);
maximize(ans , tot);
}
cout << -ans;
}
}
namespace subtask2{
bool check(){
return n == k;
}
//... solveing_
struct Node{
int l , r;
bool operator < (const Node&other) {
if (l != other.l) return l < other.l;
return r < other.r;
}
};
LL calc(vector<Node>&data){
sort(data.begin() , data.end());
LL res = inf;
vector<int> nen , lef , rig;
for(int i = 0; i < data.size(); ++i){
nen.push_back(data[i].l) , nen.push_back(data[i].r);
lef.push_back(data[i].l) , rig.push_back(data[i].r);
}
compress(nen);
sort(lef.begin() , lef.end());
sort(rig.begin() , rig.end());
LL sum_lef = 0 , sum_rig = 0;
LL sl_lef = 0 , sl_rig = 0;
for(int i = 0; i < sz(lef); ++i){
++sl_lef;
sum_lef += lef[i];
}
for(int i = 0 , ptr_lef = 0 , ptr_rig = 0; i < sz(nen); ++i){
while (ptr_rig < sz(rig) && rig[ptr_rig] < nen[i]){
sum_rig += rig[ptr_rig];
++sl_rig;
++ptr_rig;
}
while (ptr_lef < sz(lef) && lef[ptr_lef] < nen[i]){
sum_lef -= lef[ptr_lef];
--sl_lef;
++ptr_lef;
}
LL cost = sl_rig * nen[i] - sum_rig + sum_lef - sl_lef * nen[i];
minimize(res , cost);
}
return res;
}
void main_code(){
vector<Node> v;
for(int i = 1; i <= n; ++i) v.push_back({x[i] - p[i] , x[i] + p[i]});
cout << calc(v) << '\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".ans","w",stdout);
}
cin >> n >> k;
FOR(i , 1 , n) {
cin >> x[i] >> p[i] >> s[i];
}
if (subtask2::check()) return subtask2::main_code() , 0;
if (subtask1::check()) return subtask1::main_code() , 0;
assert(false);
return 0;
}
