#include <iostream>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>
const long long INF=1E9+7;
using namespace std;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    long long id_serv, id, beg, idserv, now, i, n, m, ans=INF; cin >> n >> m;
    vector<pair<pair<long long, long long>, pair<long long, long long>>> v(n);
    vector<pair<long long, long long>> cash;
    for(i=0; i<n; ++i){
        cin >> v[i].first.second >> v[i].second.first >> v[i].second.second;
        v[i].first.first=i;
    }
    while(true){
        cash=vector<pair<long long, long long>>();
        now=0;
        for(auto x:v){
            cash.push_back({x.first.first, now});
            now+=x.first.second;
        }
        set<pair<long long, long long>> servs;
        vector<pair<long long, long long>> ready;
        for(i=0; i<m; ++i) servs.insert({0, i});
        for(auto x:cash){
            id=x.first;
            beg=max((*servs.begin()).first, x.second);
            id_serv=(*servs.begin()).second;
            servs.erase(*servs.begin());
            servs.insert({beg+v[id].second.first, id_serv});
            ready.push_back({beg+v[id].second.first, id});
        }
        sort(ready.begin(), ready.end());
        for(auto x:ready) now=max(now, x.first)+v[x.second].second.second;
        ans=min(ans, now);
        if(!next_permutation(v.begin(), v.end())) break;
    }
    cout << ans;
    return 0;
}