#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);
//freopen("input.txt", "r", stdin);
//회의는 시작시간을 기준으로 오름차순 정렬한다.
//모든 회의를 지운다고 계산 했을 때 가장 w를 많이 챙기는 방법을 택한다.
//자신에서 끝점은 항상 고정한다 -> 겹칠 때 자신보다 끝 값이 큰 친구에게 끌려감, 자신보다 끝 값이 작은 친구는 포용
//k개의 큰 값을 관리하는 우선순위 큐로 관리
//자신의 끝 값이 cur의 시작 값보다 작으면 영원히 겹칠 일 없으니까 mx만 택하기
//cur에서 나가지 않은 값들과는 모두 겹치므로 자신보다 e 가 크면 들어가는 입장, 아니라면 넣는 입장이 된다.
//구현의 편의 상 자신이 빠져나간다고 해도 된다. 끝 값보다 짧아지므로 상관 없음
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;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;
}