#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<pair<int, int>, pair<int, int>>> vals;
vector<vector<pair<int, int>>> mem;
struct node {
int s, e, m, v, v1, lazy, lazys, optv;
node* l, * r;
node(int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), v(1e15), v1(0), lazy(0), lazys(0), optv(0) {
if (s != e)
l = new node(s, m),
r = new node(m + 1, e);
}
void prop() {
if (s == e) return;
if (lazys) {
l->lazys = r->lazys = l->v1 = r->v1 = lazys;
l->v = r->v = l->lazy = r->lazy = 0;
l->optv = r->optv = 0;
lazys = 0;
}
if (lazy == 0) return;
l->v += lazy;
r->v += lazy;
l->lazy += lazy;
r->lazy += lazy;
l->v1 += lazy;
r->v1 += lazy;
lazy = 0;
}
void upd(int a, int b, int x) {
if (b < s || a > e) return;
if (a <= s && b >= e) {
v += x;
v1 += x;
lazy += x;
return;
}
prop();
l->upd(a, b, x);
r->upd(a, b, x);
v = min(l->v, r->v);
v1 = min(l->v1, r->v1);
if (l->v1 < r->v1) optv = l->optv;
else optv = r->optv;
}
void upds(int n, int x, int o) {
if (s == e) {
if (v1 > x) {
v1 = x;
optv = o;
}
return;
}
prop();
if (n <= m) l->upds(n, x, o);
else r->upds(n, x, o);
if (l->v1 < r->v1) optv = l->optv;
else optv = r->optv;
v1 = min(l->v1, r->v1);
}
int qry(int a, int b) {
if (a < 0) return 0;
if (b < s || a > e) return 1e15;
if (a <= s && b >= e) return v;
prop();
return min(l->qry(a, b), r->qry(a, b));
}
pair<int, int> qry1(int a, int b) {
if (b < s || a > e) return { 1e15, 0 };
if (a <= s && b >= e) return { v1, optv };
prop();
auto rl = l->qry1(a, b), rr = r->qry1(a, b);
if (rl.first < rr.first) return rl;
return rr;
}
} *root;
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, M, K, a, b, c; cin >> N >> M >> K;
vector<pair<int, int>> vals1;
for (int i = 0; i < M; i++) {
cin >> a >> b >> c; a--, b--;
vals.push_back({ {b, a}, {c, i} });
vals1.push_back({ a, i });
}
sort(vals.begin(), vals.end());
for (int i = 0; i < M; i++) vals1[vals[i].second.second].second = i;
sort(vals1.begin(), vals1.end());
root = new node(0, N);
int fans = 1e15;
int low = 0, high = 1e15;
while (low <= high) {
vector<pair<int, int>> mem(M, { -1, -1 });
int lambda = (low + high) / 2;
root->lazys = 1e15;
root->v = 0;
root->v1 = 1e15;
root->lazy = 0;
root->optv = 0;
root->upds(N, 0, 0);
int idx1 = M - 1, idx2 = M - 1;
while (idx2 >= 0) {
//cout << idx1 << ' ' << idx2 << '\n';
//for (int i = 0; i <= N; i++) cout << root->qry(i, i) << ' ';
//cout << '\n';
//for (int i = 0; i <= N; i++) cout << root->qry1(i, i) << ' ';
//cout << "\n\n";
if (vals1[idx1].first < vals[idx2].first.first) {
mem[idx2] = root->qry1(vals[idx2].first.first + 1, N);
mem[idx2].first += lambda;
mem[idx2].second++;
idx2--;
}
else {
root->upd(vals[vals1[idx1].second].first.first + 1, N, vals[vals1[idx1].second].second.first);
root->upds(vals[vals1[idx1].second].first.first, root->qry(vals[vals1[idx1].second].first.first, vals[vals1[idx1].second].first.first) + mem[vals1[idx1].second].first, mem[vals1[idx1].second].second);
idx1--;
}
}
int crnts = 0, ans = 1e15, optv = 0;
for (int i = 0; i < M; i++) {
if (crnts + mem[i].first < ans) {
optv = mem[i].second;
ans = crnts + mem[i].first;
}
crnts += vals[i].second.first;
}
if (crnts < ans) {
optv = 0;
ans = crnts;
}
if (optv <= K) {
high = lambda - 1;
fans = min(fans, ans - optv * lambda);
}
else low = lambda + 1;
}
cout << fans << '\n';
}
