#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5,M=90000;
const ll INF=1e15;
int n,m,e;
struct node{
int l,r,w;
bool operator< (const node &t) const
{
return r<t.r;
}
}range[N];
struct Node{
int l,r;
ll v;
}tr[M*4];
void pushup(int u)
{
tr[u].v=min(tr[u<<1].v,tr[u<<1|1].v);
}
void build(int u,int l,int r)
{
tr[u]={l,r,INF};
if(l==r)
return ;
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
}
void update(int u,int k,ll v)
{
if(tr[u].l==tr[u].r)
{
tr[u].v=min(tr[u].v,v);
return ;
}
int mid=tr[u].l+tr[u].r>>1;
if(k<=mid)
update(u<<1,k,v);
else
update(u<<1|1,k,v);
pushup(u);
}
ll query(int u, int l, int r)
{
if (tr[u].l>=l&&tr[u].r<=r)
return tr[u].v;
int mid=tr[u].l+tr[u].r>>1;
ll res=INF;
if(l<=mid)
res=query(u<<1,l,r);
if(r>mid)
res=min(res,query(u<<1|1,l,r));
return res;
}
int main()
{
scanf("%d%d%d",&n,&m,&e);
//只需要覆盖这个区间
//所以线段树也只建这个区间
build(1,m-1,e);
update(1,m-1,0);
for (int i=0;i<n;i++)
{
int l,r,w;
scanf("%d%d%d",&l,&r,&w);
range[i]={l,r,w};
}
sort(range,range+n);
for (int i=0;i<n;i++)
{
int l=range[i].l,r=range[i].r,w=range[i].w;
ll v=query(1,l-1,r-1)+w; // f[r]
update(1,r,v);
}
ll res=query(1,e,e);
if (res==INF)
res=-1;
printf("%lld\n", res);
return 0;
}
AcWing 296. 清理班次2 线段树优化dp