#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int long long
#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{
LL 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<LL> nen , lef , rig;
for(int i = 0; i < data.size(); ++i){
nen.push_back(data[i].l) , nen.push_back(data[i].r);
}
compress(nen);
for(int i = 0; i < sz(nen) ;++i){
LL sum = 0;
for(int j = 0; j < data.size(); ++j){
if (data[j].l <= nen[i] && nen[i] <= data[j].r) continue;
if (nen[i] >= data[j].r) sum += nen[i] - data[j].r; else sum += data[j].l - nen[i];
}
minimize(res , sum);
}
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;
}
}
int32_t 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 (subtask1::check()) return subtask1::main_code() , 0;
return 0;
}
