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 <stdio.h>

#include <algorithm>

#include <string.h>

#include <iostream>

#include <string>

#include <queue>

using namespace std;

const int MAXN = ;

const int MAXM = ;

const int INF = 0x3f3f3f3f;

struct Edge

{

    int to,next,cap,flow,cost;

}edge[MAXM];

int head[MAXN],tol;

int pre[MAXN],dis[MAXN];

bool vis[MAXN];

int N;//节点总个数，节点编号从0~N-1

void init(int n)

{

    N = n;

    tol = ;

    memset(head,-,sizeof(head));

}

void addedge(int u,int v,int cap,int cost)

{

    edge[tol].to = v;

    edge[tol].cap = cap;

    edge[tol].cost = cost;

    edge[tol].flow = ;

    edge[tol].next = head[u];

    head[u] = tol++;

    edge[tol].to = u;

    edge[tol].cap = ;

    edge[tol].cost = -cost;

    edge[tol].flow = ;

    edge[tol].next = head[v];

    head[v] = tol++;

}

bool spfa(int s,int t)

{

    queue<int>q;

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

    {

        dis[i] = INF;

        vis[i] = false;

        pre[i] = -;

    }

    dis[s] = ;

    vis[s] = true;

    q.push(s);

    while(!q.empty())

    {

        int u = q.front();

        q.pop();

        vis[u] = false;

        for(int i = head[u]; i != -;i = edge[i].next)

        {

            int v = edge[i].to;

            if(edge[i].cap > edge[i].flow &&

               dis[v] > dis[u] + edge[i].cost )

            {

                dis[v] = dis[u] + edge[i].cost;

                pre[v] = i;

                if(!vis[v])

                {

                    vis[v] = true;

                    q.push(v);

                }

            }

        }

    }

    if(pre[t] == -)return false;

    else return true;

}

//返回的是最大流，cost存的是最小费用

int minCostMaxflow(int s,int t,int &cost)

{

    int flow = ;

    cost = ;

    while(spfa(s,t))

    {

        int Min = INF;

        for(int i = pre[t];i != -;i = pre[edge[i^].to])

        {

            if(Min > edge[i].cap - edge[i].flow)

                Min = edge[i].cap - edge[i].flow;

        }

        for(int i = pre[t];i != -;i = pre[edge[i^].to])

        {

            edge[i].flow += Min;

            edge[i^].flow -= Min;

            cost += edge[i].cost * Min;

        }

        flow += Min;

    }

    return flow;

}

pair<int,int>p[];

int main()

{

    int T;

    int n,k;

    scanf("%d",&T);

    while(T--)

    {

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

        init(*n+);

        int a,b,w;

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

        {

            scanf("%d%d%d",&a,&b,&w);

            p[i] = make_pair(a,b);

            addedge(*i-,*i,,-w);

            addedge(*i-,*i,INF,);

            addedge(,*i-,,);

            addedge(*i,*n+,,);

        }

        addedge(*n+,,k,);

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

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

                if(p[j].first >= p[i].second )

                    addedge(*i,*j-,INF,);

        int cost = ;

        minCostMaxflow(*n+,*n+,cost);

        printf("%d\n",-cost);

    }

    return ;

}