#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010;
int n, m;
struct P {
	int l, r, w;
}; P a[N];
vector<int> p; int lp;
ll f[N];
multiset<int> st;
vector<int> veclb[N];

int main() {
	ios::sync_with_stdio(0); cin.tie(nullptr);
	cin >> n >> m;
	p.reserve(2 * n);
	for(int i = 1; i <= n; i++) {
		cin >> a[i].l >> a[i].r >> a[i].w;
		p.push_back(a[i].l), p.reserve(a[i].r);
	}
	sort(p.begin(), p.end()), p.resize(unique(p.begin(), p.end()) - p.begin());
	lp = p.size();
	for(int i = 1; i <= n; i++) {
		a[i].l = lower_bound(p.begin(), p.end(), a[i].l) - p.begin() + 1;
		a[i].r = lower_bound(p.begin(), p.end(), a[i].r) - p.begin() + 1;
	}
	sort(a + 1, a + n + 1, [](P x, P y) { return x.r < y.r; });
	f[0] = 1;
	int pos = 0;
	for(int i = 1; i <= lp; i++) {
		for(; pos < n && a[pos + 1].r <= i;) {
			++pos;
			veclb[a[pos + 1].l].push_back(a[pos + 1].w);
		}
		ll sum = 0;
		f[i] = f[i - 1];
		st.clear();
		for(int j = i; j; j--) {
			for(auto v : veclb[j]) {
				sum += v;
				st.insert(v);
				for(; st.size() > m;) {
					sum -= *st.begin();
					st.erase(st.begin());
				}
			}
			f[i] = max(f[i], f[j - 1] + sum);
		}
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++) ans += a[i].w;
	cout << ans - f[lp] << "\n";
	return 0;
}