#include <iosream>
#include<vector>
#include<set>
#include<algorithm>
#include<array>
#include<queue>
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 + 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;
}