#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef pair<int, int> pi;
typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n,k;cin>>n>>k;
    vector<array<ll,3>>v(n);
    for(int i=0;i<n;i++) cin>>v[i][0]>>v[i][1]>>v[i][2];
    sort(v.begin(),v.end());
    vector<priority_queue<ll,vector<ll>,greater<ll>>>pq(n);
    vector<ll>d(n);
    ll sum=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(v[i][1]>=v[j][1]){
                pq[i].push(v[j][2]);
                d[i]+=v[j][2];
                if(pq[i].size()>k){
                    d[i]-=pq[i].top();
                    pq[i].pop();
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        auto &cur=v[i];
        sum+=cur[2];
        int e=i-1;
        multiset<ll,greater<ll>>s;
        s.insert(0);
        for(int j=0;j<i;j++) s.insert(d[j]);
        ll mx=d[i];
        for(int j=i;j>=0;j--){
            if(v[j][1]<cur[0]) break;
            if(v[j][1]>v[i][1]) continue;
            while(e>=0&&v[e][1]>=v[j][0]){
                auto it=s.find(d[e--]);
                s.erase(it);
            }
            ll base=*s.begin();
            pq[i].push(v[j][2]);
            d[i]+=v[j][2];
            if(pq[i].size()>k){
                d[i]-=pq[i].top();
                pq[i].pop();
            }
            mx=max(mx,d[i]+base);
        }
        d[i]=mx;
        //cout<<i<<" : "<<mx<<"\n";
    }
    ll ans=0;
    for(auto i:d) ans=max(ans,i);
    cout<<sum-ans;
}

/usr/bin/ld: /tmp/cc4Dya9u.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccoLoGIs.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccoLoGIs.o: in function `main':
implementer.cpp:(.text.startup+0x23b): undefined reference to `min_charge(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status