#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
const int N = 1e2 + 5;
vector<pair<int, int>> vp[N];
const int inf = 1e15;
int n, m, k;
struct SegTree {
pair<int, int> aint[4 * N + 5];
pair<int, int> lazy[4 * N + 4];
int n;
SegTree(int _n) {
n = _n;
build(1, 1, n);
}
void propag(int x) {
aint[x].first += lazy[x].first;
aint[x].second += lazy[x].second;
if (2 * x + 1 < 4 * N + 5) {
lazy[2 * x].first += lazy[x].first;
lazy[2 * x].second += lazy[x].second;
lazy[2 * x + 1].first += lazy[x].first;
lazy[2 * x + 1].second += lazy[x].second;
}
lazy[x] = {0, 0};
}
void build(int pos, int st, int dr) {
aint[pos] = {-inf, 0};
lazy[pos] = {0, 0};
if (st == dr) {
return;
}
int mid = (st + dr) / 2;
build(2 * pos, st, mid);
build(2 * pos + 1, mid + 1, dr);
}
void update(int pos, int st, int dr, int l, int r, pair<int, int> val) {
propag(pos);
if (l <= st && dr <= r) {
lazy[pos] = val;
propag(pos);
return;
}
int mid = (st + dr) / 2;
if (l <= mid) {
update(2 * pos, st, mid, l, r, val);
} else {
propag(2 * pos);
}
if (mid < r) {
update(2 * pos + 1, mid + 1, dr, l, r, val);
} else {
propag(2 * pos + 1);
}
aint[pos] = max(aint[2 * pos], aint[2 * pos + 1]);
}
pair<int, int> query(int pos, int st, int dr, int l, int r) {
propag(pos);
if (l <= st && dr <= r) {
return aint[pos];
}
int mid = (st + dr) / 2;
if (r <= mid) {
return query(2 * pos, st, mid, l, r);
} else if (mid < l) {
return query(2 * pos + 1, mid + 1, dr, l, r);
} else {
return max(query(2 * pos, st, mid, l, r), query(2 * pos + 1, mid + 1, dr, l, r));
}
}
};
pair<int, int> greedy(int lambda) {
vector<pair<int, int>> dp(n + 1);
SegTree ds(n + 1);
ds.update(1, 1, n + 1, 1, 1, {inf, 0});
for (int i = 1; i <= n; i ++) {
for (auto j : vp[i]) {
ds.update(1, 1, n + 1, j.first, i - 1, {j.second, 0});
}
auto x = ds.query(1, 1, n + 1, 1, n + 1);
dp[i] = max(dp[i - 1], {x.first - lambda, x.second - 1});
ds.update(1, 1, n + 1, i + 1, i + 1, {inf + dp[i].first, dp[i].second});
cout << lambda << " " << dp[i].first << " " << dp[i].second << '\n';
}
return {dp[n].first, -dp[n].second};
}
signed main() {
cin >> n >> m >> k;
int sum = 0;
for (int i = 0; i < m; i ++) {
int s, t, c;
cin >> s >> t >> c;
vp[t].push_back({s, c});
sum += c;
}
int lambda = 0;
for (int pas = 1ll << 50; pas; pas >>= 1) {
if (greedy(lambda + pas).second >= k) {
lambda += pas;
}
}
int ans = greedy(lambda).first + k * lambda;
cout << sum - ans << '\n';
}
