题目链接

<h2>题解</h2>

一个我想不到的性质：每个点至多会被覆盖两次。
因为如果一个点被覆盖三次，那么肯定有一条线段的效果是可以被另外两条完全表达出来的，所以可以删去这个线段。
我们先将线段按照右端点排个序，有了这个性质，又因为它是个最优化问题，启发我们设 $f_{i,j}$ 表示考虑到了前 $i$ 个线段，最后一段被覆盖了一次的线段是 $[j,r_i]$ 的最小代价。答案就是所有 $r_i = n$ 的 $f_{i,*}$ 的最小值。
考虑转移：我们枚举上一条线段 $j$，如果 $r_j &lt; l_i$ 那么显然不能转移（会留下空），但是我们也要注意如果 $j$ 是被 $i$ 完全包含的也不能从这里转移，因为会少算其它线段的影响（没错我一开始就挂了）。分类讨论：

1. $r_j + 1 = l_i$，所以 $[l_i,r_i]$ 没有被覆盖过，$f_{j,[1,r_i]}$ 和 $w_i$ 取 max。
2. $r_j \in [l_i,r_i)$，所以有一段被覆盖过，$f_{j,[1,l_i]}$ 和 $w_i+w_j$ 取 max。
   直接转移是 $O(n^2m)$ 的，使用前缀和优化可以做到 $O(n^2+nm)$。

<h2>代码</h2>

/*
 * Author: RainAir
 * Time: 2019-10-27 15:07:46
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3000+5;

struct Node{
    int l,r,w;
    bool operator < (const Node &t) const {
        return r == t.r ? l < t.l : r < t.r;
    }
}a[MAXN];
int n,m;
int fMAXN,gMAXN,hMAXN;
// f:f g:min h:pos

inline void Solve(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].w);
    std::sort(a+1,a+n+1);
    FOR(i,0,n+1) FOR(j,0,m+1) fi = gi = 1e9,hi = -1;
  //  FOR(i,1,n){
 //       printf("%d %d %dn",a[i].l,a[i].r,a[i].w);
 //   }
    FOR(i,1,n){
        if(a[i].l == 1) fi = a[i].w;
        FOR(j,1,i-1){
            if(a[j].l >= a[i].l) continue;
            if(a[j].r == a[i].r) continue;
            if(a[j].r >= a[i].l){
    //            if(a[j].r+1 == 16 && i == n) DEBUG(j);
                fi.r+1] = std::min(fi.r+1],std::max(a[i].w+a[j].w,gj.l]));
            }
            else{
                if(a[j].r+1 == a[i].l){
                    if(hj.r] != -1){
                        fi[a[j].r]] = std::min(fi[a[j].r]],std::max(a[i].w,gj.r]));
                    }
                }
            }
        }
//        if(i == 12) {FOR(j,1,m) printf("%d ",fi);puts("");}
        FOR(j,1,a[i].r){
            gi = gi,hi = hi;
            if(fi < gi){
                gi = fi;
                hi = j;
            }
        }
    }
    int ans = 1e9;
    //FOR(i,1,n) if(a[i].r == m) DEBUG(gi);
    FOR(i,1,n) if(a[i].r == m) ans = std::min(ans,gi);
    printf("%dn",ans == 1e9 ? -1 : ans);
//    exit(0);
}

int main(){
    freopen("intervals.in","r",stdin);
    freopen("intervals.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}