考虑如何能跳出这个最长路：如果当前在位置 $i$，我们考虑找到最小的 $t_j$，满足 $i\le s_j\le t_j$，然后从 $i$ 跳到 $t_j$。

那么可以设 $f_{i,k}$ 表示 跳到了 $i$，最长路为 $k$ 的最小代价。转移方程为：$f_{i,k}=\min_{j<i}\{f_{j,k-1}+\sum_{[s_p,t_p]\sub[j,i)}C_p\}$。后面的代价函数是典型的“区间子区间”类的形式，只要 $C$ 非负就一定满足四边形不等式。从而 $f_{i,*}$ 关于第二维有凸性。

从而我们 wqs 二分，去掉第二维。容易使用线段树维护剩下的 dp。时间复杂度 $O(n\log n\log V)$。

#include<bits/stdc++.h>
#define mid (l+r>>1)
#define ls (k<<1)
#define rs (k<<1|1)
#define pii pair<ll,int>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,m,k,g[N];
vector<pii> V[N];
ll tag[N];pii s[N];
ll f[N],ans=2e18;
void build(int k,int l,int r){
    tag[k]=0;
    s[k].first=2e18;s[k].second=0;
    if(l==r)return;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void due(int k,ll z){
    s[k].first+=z;
    tag[k]+=z;
}
void pushdown(int k){
    if(!tag[k])return;
    due(ls,tag[k]);
    due(rs,tag[k]);
    tag[k]=0;
}
void change(int k,int l,int r,int x,int y,ll z){
    if(l>y||r<x)return;
    if(l>=x&&r<=y){
        due(k,z);
        return;
    }pushdown(k);
    change(ls,l,mid,x,y,z);
    change(rs,mid+1,r,x,y,z);
    s[k]=min(s[ls],s[rs]);
}
void modify(int k,int l,int r,int x){
    if(l==r){
        s[k].first=f[l];
        s[k].second=g[l];
        return;
    }
    pushdown(k);
    if(x<=mid)modify(ls,l,mid,x);
    else modify(rs,mid+1,r,x);
    s[k]=min(s[ls],s[rs]);
}
int check(ll d){
    int p=1;
    build(1,0,n);f[0]=0;g[0]=0;
    modify(1,0,n,0);
    for(int i=1;i<=n;i++){
        for(pii tmp:V[i])change(1,0,n,0,tmp.first-1,tmp.second);
        f[i]=s[1].first+d;g[i]=s[1].second+1;
        modify(1,0,n,i);
    }
    return g[n];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;k=min(k+1,n);
    for(int i=1;i<=m;i++){
        int x,y,z;cin>>x>>y>>z;
        V[y].emplace_back(x,z);
    }
    ll l=-1,r=1e14,ss=0;
    while(l<=r){
        ll mm=(l+r>>1);
        if(check(mm)<=k)ss=mm,r=mm-1;
        else l=mm+1;
    }
    check(ss);
    cout<<f[n]-ss*k<<'\n';
	return 0;
}