#include <stdio.h>

int n;
int VM;
int v[11];
float t[11], d[11][11];
float H;
int w[11];
char av[11];

void search (int c)
{
  int V;
  float td;
  int i;

  if (c == n)
    {
      V = 0; td = 0.0;
      for (i = 1; (i < n) && (td + t[w[i]] + d[w[i-1]][w[i]] + d[w[i]][0] <= H); i ++)
	{ V += v[w[i]]; td += t[w[i]] + d[w[i-1]][w[i]]; }
      if (V > VM) VM = V;
      if (t[w[0]] <= H)
	{
	  V = v[w[0]]; td = t[w[0]];
	  for (i = 1; (i < n) && (td + t[w[i]] + d[w[i-1]][w[i]] + d[w[i]][0] <= H); i ++)
	    { V += v[w[i]]; td += t[w[i]] + d[w[i-1]][w[i]]; }
	  if (V > VM) VM = V;
	}
    }
  else
    for (w[c] = 1; w[c] < n; w[c] ++)
      if (!av[w[c]])
	{
	  av[w[c]] = 1;
	  search (c+1);
	  av[w[c]] = 0;
	}
}

int main (void)
{
  int K, k;
  int i, j;

  FILE *in = fopen ("stops.in", "r");
  fscanf (in, "%d\n", &K);
  for (k = 1; k <= K; k ++)
    {
      fscanf (in, "%d %f\n", &n, &H);
      for (i = 0; i < n; i ++)
	fscanf (in, "%d %f\n", &v[i], &t[i]);
      for (i = 0; i < n; i ++)
	{
	  for (j = 0; j < n; j ++)
	    fscanf (in, "%f ", &d[i][j]);
	  fscanf (in, "\n");
	}
      w[0] = 0; VM = 0;
      for (i = 0; i < n; i ++) av[i] = 0;
      search (1);
      printf ("Data Set %d:\n%d\n", k, VM);
    }
  fclose (in);
  return 0;
}