#include <iostream>
#include <string>
#include <math.h>
#include <sstream>
#include <fstream>

using namespace std;
/*

string get_line(fstream &file)
{
char temp[256];
string t;
file.getline(temp,256);
t = temp;
return t;
}
*/

struct visit
{
	int v;
	double t;
};

double travel[10][10];
visit plan[10];
int locs;
double hours;
int max_votes;

bool get_bit(int v, int x)
{
	return ((v & (1 << x)) != 0);
}

int set_bit(int v, int x)
{
return v | (1 << x);
}


void value(int loc, double t, int votes, int visited)
{
	
//	cout << loc << " " << t << " " << votes << " " << visited << "\n";
	if (loc == 0 && t <= hours)
	{
		if (votes > max_votes)
		{
			max_votes = votes;
		}
	}

	if (!get_bit(visited,loc))
	{
		t += plan[loc].t;
		votes += plan[loc].v;
	}

	if (loc == 0 && t <= hours)
	{
		if (votes > max_votes)
		{
			max_votes = votes;
		}
	}


	visited = set_bit(visited,loc);

	for(int i = 0; i < locs; i++)
	{
		if (!get_bit(visited,i) || (i == 0 && loc != 0))
		{
			if ((t + travel[loc][i]) <= hours)
				value(i,t+travel[loc][i],votes,visited);
		}

	}
}


int main()
{

fstream file("stops.in");

int sets;
file >> sets;


for(int a = 0; a < sets; a++)
	{
	int s;
	double h;
	file >> s >> h;

	locs = s;
	hours = h;

	for(int i = 0; i < s; i++)
	{
		file >> plan[i].v;
		file >> plan[i].t;
	}

	for(int i = 0; i < s; i++)
	{
		for(int j = 0; j < s; j++)
		{
			file >> travel[i][j];
		}
	}
	
	max_votes = 0;

	for(int i = 0; i < locs; i++)
		value(i,(i == 0) ? 0 : travel[0][i],0,0);

	cout << "Data Set " << (a + 1) << ":\n";
	cout << max_votes << "\n";
}



return 0;
}