#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 2510,M = 5e6 + 10,INF = 1e9;
int T,n,m;
struct Node
{
    int l,r,w;
    bool operator<(const Node & W) const
    {
        return r < W.r;
    }
};
int f[N];
priority_queue<int,vector<int>,greater<int>> heap;
vector<Node> nodes;
vector<int> tmp;

void solve()
{
    cin >> n >> m;
    int tot = 0;
    for(int i = 1;i <= n;i++)
    {
        int l,r,w;
        cin >> l >> r >> w;
        nodes.push_back({l,r,w});
        tmp.push_back(l);
        tmp.push_back(r);
        tot += w;
    }
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    for(int i = 0;i < n;i++)
    {
        auto &cur = nodes[i];
        int posl = lower_bound(tmp.begin(), tmp.end(), cur.l) - tmp.begin() + 1;
        int posr = lower_bound(tmp.begin(), tmp.end(), cur.r) - tmp.begin() + 1;
        cur.l = posl,cur.r = posr;
    }
    sort(nodes.begin(),nodes.end());
    nodes.push_back({-INF,INF,0});
    for(int i = 0;i <= n;i++)
    {
        int sum = 0,tmpl = 0;
        if(i) tmpl = nodes[i - 1].l;
        while(heap.size()) heap.pop();
        for(int j = i - 1;j >= 0;j--)
        {
            if(nodes[j].r >= tmpl)
            {
                if(heap.size() < m)
                {
                    heap.push(nodes[j].w);
                    sum += nodes[j].w;
                }
                else if(nodes[j].w > heap.top())
                {
                    sum -= heap.top();
                    heap.pop();
                    sum += nodes[j].w;
                    heap.push(nodes[j].w);
                }
                tmpl = min(tmpl,nodes[j].l);
                f[i + 1] = max(f[i + 1],f[j] + sum);
            }
            else{
                f[i + 1] = max(f[i + 1],f[j + 1] + sum + nodes[j].w);
                break;
            }
        }
    }
//     for(int i = 1;i <= n + 1;i++)
//     {
//         cout << f[i] << ' ';
//     }
//     cout << endl;
    cout << tot - f[n + 1] << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    T = 1;
    while(T--)
    {
        solve();
    }
}