#include <bits/stdc++.h>

using namespace std;

const int VMAX = 91002;
const int INF = 1e9;

struct edge {
    int x;
    int y;
    int flux_go;
    int flux_rev;
    int cost_go;
    int cost_rev;
    inline int vec( int a ) {
        return x + y - a;
    }
    inline int flux( int a ) {
        if ( a == x ) return flux_go;
        return flux_rev;
    }
    inline int cost( int a ) {
        if ( a == x ) return cost_go;
        return cost_rev;
    }
};
vector <edge> muchii;

vector <int> edges[VMAX + 1];

int dist[VMAX + 1];
int fakedist[VMAX + 1];
int realdist[VMAX + 1];

bool inq[VMAX + 1];

int n, g, s, d;

void bellman( int node ) {
    for ( int i = 0; i <= d; i ++ ) dist[i] = INF;
    queue <int> q;
    q.push( node );
    dist[node] = 0;
    while ( !q.empty() ) {
        node = q.front();
        q.pop();
        inq[node] = 0;
        for ( auto i : edges[node] ) {
            int x = muchii[i].vec( node );
            if ( muchii[i].flux( node ) > 0 && dist[node] + muchii[i].cost( node ) < dist[x] ) {
                dist[x] = dist[node] + muchii[i].cost( node );
                if ( !inq[x] ) {
                    q.push( x );
                    inq[x] = 1;
                }
            }
        }
    }
}

static inline int cod( int camera, int greutate ) {
    return camera * ( g + 1 ) + greutate;
}
int p[VMAX + 1];
bool viz[VMAX + 1];

bool flow() {
    for ( int i = 0; i <= d; i ++ ) {
        p[i] = -2;
        fakedist[i] = INF;
        realdist[i] = dist[i];
        viz[i] = false;
    }
    priority_queue <pair<int, int>> pq;
    pq.push( { 0, s } );
    fakedist[s] = dist[s] = 0;
    p[s] = -1;
    while ( !pq.empty() ) {
        int node = pq.top().second;
        pq.pop();
        if ( viz[node] ) continue;
        viz[node] = 1;
        for ( auto i : edges[node] ) {
            int x = muchii[i].vec( node );
//            if ( node == 0 && x == 4 ) cout << muchii[i].flux( node ) << endl;
            if ( muchii[i].flux( node ) > 0 && ( p[x] == -2 || fakedist[node] + realdist[node] + muchii[i].cost( node ) - realdist[x] < fakedist[x] ) ) {
                p[x] = i;
                fakedist[x] = fakedist[node] + realdist[node] + muchii[i].cost( node ) - realdist[x];
                dist[x] = dist[node] + muchii[i].cost( node );
                pq.push( { -fakedist[x], x } );
            }
        }
    }
    return fakedist[d] != INF;
}

ifstream fin( "hoata2.in" );
ofstream fout( "hoata2.out" );

void add_edge( int a, int b, int flux, int cost ) {
    int i = muchii.size();

    muchii.push_back( edge{ a, b, flux, 0, cost, -cost } );
    edges[a].push_back( i );
    edges[b].push_back( i );
}
pair <int, int> decode( int cod ) {
    return { cod / ( g + 1 ), cod % ( g + 1 ) };
}
void solve() {
    int k;
    fin >> n >> k >> g;
    s = cod( n, 0 );
    d = cod( n, 1 );
    add_edge( s, 0, k, 0 );
    for ( int i = 0; i < n; i ++ ) {
        int v, w, x;
        fin >> v >> w >> x;
        for ( int j = 0; j + w <= g; j ++ ) {
            add_edge( cod( i, j ), cod( i, j + w ), INF, -v );
        }
        for ( int j = 0; j <= g; j ++ ) {
            if ( i + 1 < n ) {
                add_edge( cod( i, j ), cod( i + 1, j ), x, 0 );
            } else {
                add_edge( cod( i, j ), d, x, 0 );
            }
        }
    }
    bellman( s );
    int maxflow = 0, mincost = 0;
    while ( flow() ) {
        int f = INF, c = 0;
        for ( int i = d; i != s; i = muchii[p[i]].vec( i ) ) {
            f = min( f, muchii[p[i]].flux( muchii[p[i]].vec( i ) ) );
            c += muchii[p[i]].cost( muchii[p[i]].vec( i ) );
        }
        maxflow += f;
        mincost += c * f;
        for ( int i = d; i != s; i = muchii[p[i]].vec( i ) ) {
            int previous = muchii[p[i]].vec( i ), x = muchii[p[i]].x;
            if ( previous == x ) {
                muchii[p[i]].flux_go -= f;
                muchii[p[i]].flux_rev += f;
            } else {
                muchii[p[i]].flux_go += f;
                muchii[p[i]].flux_rev -= f;
            }
        }
    }
    if ( maxflow != k ) {
        fout << "-1\n";
    } else {
        fout << -mincost << '\n';
    }
    muchii.clear();
    for ( int i = 0; i <= d; i ++ ) {
        edges[i].clear();
    }
}
int main() {

    int t = 1;
    fin >> t;
    while ( t-- ) solve();
    return 0;
}