#include <cstdio>#include <cstring>#include <algorithm>#define eps 1e-6using namespace std;int p[100][5];int T,N,D;int d[100][200];int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&N,&D); int sum = 0; memset(p,0,sizeof(p)); for(int i = 1; i <= N; i++){ for(int j = 1; j <= 3; j++) scanf("%d",&p[i][j]); } memset(d,-1,sizeof(d)); d[0][0] = 0; for(int i = 0; i < N; i++){ for(int j = 0; j <= D; j++){ if(d[i][j]==-1) continue; d[i+1][j+1] = max(d[i+1][j+1],d[i][j]+p[i+1][1]); d[i+1][j+2] = max(d[i+1][j+2],d[i][j]+p[i+1][2]); d[i+1][j+3] = max(d[i+1][j+3],d[i][j]+p[i+1][3]); } } printf("%dn",d[N][D]); } return 0;}
