#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;

constexpr ll NN = 2e5, M = 1000000007, L = 20, oo = 1e14;
struct E{
    int l,r;
    ll w;
};
void run()
{
    ll n,k; cin >> n >> k;
    vector<E> v(n);
    set<int> st; map<int,int> mp; ll tot = 0;
    for(int i : rep(n)){
        cin >> v[i].l >> v[i].r >> v[i].w; tot+=v[i].w;
        st.insert(v[i].l),st.insert(v[i].r);
    }
    int sz = 0; for(int x : st) mp[x]=sz++;
    for(auto &[l,r,_] : v) l=mp[l],r=mp[r];
    ranges::sort(v,[](E a,E b){return a.r<b.r;}); //sort by right endpt
    vector<vll> cost(sz,vll(sz,0)); //populate cost
    for(int l : rep(sz)){
        priority_queue<ll,vll,greater<>> pq; ll sm = 0; int idx = 0;
        for(int r : rep(l,sz)){
            while(idx<n and v[idx].r <= r){
                if(v[idx].l < l) {idx++;continue;} //dont consider this range
                if(len(pq)<k) sm+=v[idx].w,pq.push(v[idx].w);
                else if(pq.top() < v[idx].w) sm-=pq.top(),pq.pop(),sm+=v[idx].w,pq.push(v[idx].w);
                ++idx;
            } cost[l][r] = sm;
        }
    }
    vll dp(sz);
    for(int i : rep(0,sz)){
        dp[i] = cost[0][i];
        for(int j : rep(1,i))
            dp[i] = max(dp[i],dp[j-1]+cost[j][i]);
    }

    cout << tot-dp[sz-1] << '\n';
    // ranges::copy(dp,oit<ll>()),cout << '\n';
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    cin.tie(0);
    run();
}