#include<bits/stdc++.h>
using namespace std;
struct Segment{
	int l,r,w;
}a[2001];
using ll=long long;
priority_queue<ll,vector<ll>,greater<ll>>q;
ll g[4001][4001];
ll dp[4001];
vector<int>dat;
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	long long all=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d %d",&a[i].l,&a[i].r,&a[i].w);
		dat.push_back(a[i].l);
		dat.push_back(a[i].r);
		all+=a[i].w;
	}
	sort(dat.begin(),dat.end());
	dat.erase(unique(dat.begin(),dat.end()),dat.end());
	for(int i=1;i<=n;i++)
	{
		a[i].l=lower_bound(dat.begin(),dat.end(),a[i].l)-dat.begin()+1;
		a[i].r=lower_bound(dat.begin(),dat.end(),a[i].r)-dat.begin()+1;
	}
	sort(a+1,a+n+1,[&](Segment S,Segment T){
		return S.r<T.r;
	});
	int k=dat.size();
	for(int i=1;i<=k;i++)
	{
		while(!q.empty())
			q.pop();
		long long sum=0;
		int r=0;
		for(int j=1;j<=n;j++)
			if(a[j].l>=i)
			{
				r=max(r,a[j].r);
				q.push(a[j].w);
				sum+=a[j].w;
				if(q.size()>m)
				{
					sum-=q.top();
					q.pop();
				}
				g[i][r]=sum;
			}
	}
	dp[0]=0;
	for(int i=1;i<=k;i++)
		for(int j=0;j<i;j++)
			dp[i]=max(dp[i],dp[j]+g[j+1][i]);
	printf("%lld\n",all-dp[k]);

	return 0;
}