题意：牛棚需要清理打扫，打扫时段从第 MM 秒开始，第 EE 秒结束，即每天打扫的总时间为 E−M+1E-M+1 秒。

对于每一头牛，它愿意在 T1∼T2T _1\sim T _2 的时段内工作 (M≤T1≤T2≤E)(M\le T _1 \le T _2\le E)，需要 SS 元作为报酬，一旦选择某头牛打扫，即使它只工作了时段中的一部分，也要付全额报酬。

请你选择雇佣奶牛来打扫清洁，满足总花费尽量小。

一道 DP。

我们设 f[i]f[i] 代表从 MM 覆盖到 ii 的最少费用，推出状态转移方程为：

dp[i]=min⁡(dp[i],dp[k])+S (T1−1≤k≤T2−1) dp[i]=\min (dp[i],dp[k])+S\ (T _1 -1\le k \le T _2 -1)

然后按照右端点从小到大排序，求最小值用线段树优化即可(即线段树维护 dpdp 数组，执行查询最值和修改操作)。

注意：由于 MM 和 EE 可能较大，不好建立线段树，我们将其先都减掉 M−2M-2 即可(即让 M=2M=2，此时状态转移方程中用到的最小数正好是 M−1=1M-1=1)。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=2e4+101,maxm=5e5+1010;
int n,m,e,maxx;
int minn[maxm<<2],ans;
struct cow
{
	int l;
	int r;
	int s;
	bool operator<(const cow& b)const{
        return r<b.r;
    }
}a[maxn];
void pushup(int rt)
{
	minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);
}
void build(int l,int r,int rt)
{
	if(l==r)
	{
		minn[rt]=INF;
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	pushup(rt);
}
void update(int x,int val,int l,int r,int rt)
{
	if(l==r)
	{
		minn[rt]=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
		update(x,val,lson);
	else
		update(x,val,rson);
	pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R)
		return minn[rt];
	int ans=INF;
	int mid=(l+r)>>1;
	if(L<=mid)
		ans=min(ans,query(L,R,lson));
	if(R>mid)
		ans=min(ans,query(L,R,rson));
	return ans;
}
int main()
{
	scanf("%d%d%d",&n,&m,&e);
	e-=m-2;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].s);
		a[i].l-=m-2;
		a[i].r-=m-2;
	}
	m=2;
	sort(a+1,a+n+1);
	build(1,e,1);
	update(1,0,1,e,1);
	for(int i=1;i<=n;i++)
	{
		int num1=query(a[i].l-1,a[i].r-1,1,e,1);
		int num2=query(a[i].r,a[i].r,1,e,1);
		if(num1+a[i].s<num2)
			update(a[i].r,num1+a[i].s,1,e,1);
	}
	int ans=query(e,e,1,e,1);
	if(ans==INF)
		printf("-1");
	else
		printf("%d",ans);
	return 0;
}