You are given N weighted open intervals. The ith interval covers (a_i, b_i) and weighs w_i. Your task is to pick some of the intervals to maximize the total weights under the limit that no point in the real axis is covered more than k times.

The first line of input is the number of test case.
The first line of each test case contains two integers, N and K (1 ≤ K ≤ N ≤ 200).
The next N line each contain three integers a_i, b_i, w_i(1 ≤ a_i < b_i ≤ 100,000, 1 ≤ w_i ≤ 100,000) describing the intervals.
There is a blank line before each test case.

For each test case output the maximum total weights in a separate line.

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 using namespace std;

 const int INF=;

 const int maxn=,maxm=;

 int cnt,fir[maxn],nxt[maxm],to[maxm],cap[maxm],val[maxm],dis[maxn],path[maxn];

 struct data{

     int l,r,v;

     bool operator <(const data A)const{

         if(l!=A.l)

             return l<A.l;

         return r<A.r;

     }

 }ar[maxn];

 struct data2{

     int a,pos;

     bool operator <(const data2 A)const{

         if(a!=A.a)

             return a<A.a;

         return pos<A.pos;

     }

 }br[maxn];

 void addedge(int a,int b,int c,int v)

 {

     nxt[++cnt]=fir[a];to[cnt]=b;cap[cnt]=c;val[cnt]=v;fir[a]=cnt;

 }

 int S,T;

 int Spfa()

 {

     queue<int>q;

     memset(dis,-,sizeof(dis));

     q.push(S);dis[S]=;

     while(!q.empty())

     {

         int node=q.front();q.pop();

         for(int i=fir[node];i;i=nxt[i])

             if(cap[i]&&dis[node]+val[i]>dis[to[i]]){

                 dis[to[i]]=val[i]+dis[node];

                 path[to[i]]=i;

                 q.push(to[i]);

             }

     }

     return dis[T]==-?:dis[T];

 }

 int Aug()

 {

     int p=T,f=INF;

     while(p!=S)

     {

         f=min(f,cap[path[p]]);

         p=to[path[p]^];

     }

     p=T;

     while(p!=S)

     {

         cap[path[p]]-=f;

         cap[path[p]^]+=f;

         p=to[path[p]^];

     }

     return f;

 }

 int MCMF()

 {

     int ret=,d;

     while(d=Spfa())

         ret+=Aug()*d;

     return ret;

 }

 int cont;

 void Init()

 {

     cnt=;cont=;

     memset(fir,,sizeof(fir));

 }

 int main()

 {

     int Q,n,k;

     scanf("%d",&Q);

     while(Q--)

     {

         Init();

         scanf("%d%d",&n,&k);

         for(int i=;i<=n;i++)

             scanf("%d%d%d",&ar[i].l,&ar[i].r,&ar[i].v);

         sort(ar+,ar+n+);

         for(int i=;i<=n;i++){

             br[i*-].a=ar[i].l;br[i*].a=ar[i].r;

             br[i*-].pos=br[i*].pos=i;

         }

         sort(br+,br+*n+);

         for(int i=;i<=n;i++)

             ar[i].l=ar[i].r=;

         for(int i=;i<=*n;i++)

         {

             int p=br[i].pos;

             if(!ar[p].l){

                 ar[p].l=++cont;

             }

             else{

                 ar[p].r=++cont;

             }

         }

         S=;T=cont+;

         for(int i=;i<cont+;i++)

             addedge(i,i+,k,),addedge(i+,i,,);

         for(int i=;i<=n;i++)

             addedge(ar[i].l,ar[i].r,,ar[i].v),addedge(ar[i].r,ar[i].l,,-ar[i].v);

         printf("%d\n",MCMF());

     }

     return ;

 }