#include<cstdio>#include<cstring>#include<vector>#include<algorithm>using namespace std;#define pb push_backchar name[20][20]={"Head","Shoulder","Neck","Torso","Hand","Wrist","Waist","Legs","Feet","Finger","Shield","Weapon","Two-Handed"};int t, n, m;struct Goods{ int dmg, tou;}g;int getnum(char* s){ for(int i=0; i<13; i++) if(strcmp(s, name[i])==0) return i;}vector<Goods> V[13];int dp[13][50001], vd, vt;int main(){ int i, j, k; char s[20]; scanf("%d", &t); while(t--){ scanf("%d %d", &n, &m); for(i=0; i<13; i++) V[i].clear(); while(n--){ scanf("%s %d %d", s, &i, &j); k = getnum(s); V[k].pb((Goods){i,j}); if(k==11 || k==10){ V[12].pb((Goods){i,j}); } } for(i=0; i<V[11].size(); i++){ for(j=0; j<V[10].size(); j++){ V[12].pb((Goods){V[11][i].dmg+V[10][j].dmg, V[11][i].tou+V[10][j].tou}); } } V[10].clear(); for(i=0; i<V[9].size(); i++){ V[10].pb(V[9][i]); for(j=i+1; j<V[9].size(); j++){ V[10].pb((Goods){V[9][i].dmg+V[9][j].dmg, V[9][i].tou+V[9][j].tou}); } } V[9].clear(); memset(dp,-1,sizeof(dp)); dp[11][0]=0; for(i=0; i<V[12].size(); i++){ g = V[12][i]; vt = g.tou>m?m:g.tou; vd = g.dmg; dp[11][vt] = max(dp[11][vt], vd); } for(k=10; k>=0; k--){ for(j=0; j<=m; j++){ dp[k][j] = max(dp[k][j], dp[k+1][j]); if(dp[k+1][j]==-1) continue; for(i=0; i<V[k].size(); i++){ g = V[k][i]; vt = (g.tou+j)>m?m:(g.tou+j); vd = g.dmg+dp[k+1][j]; dp[k][vt] = max(dp[k][vt], vd); } } } printf("%dn", dp[0][m]); } return 0;}
