Campaign Stops

One important part of running an election-year campaign is to visit many places, give your carefully crafted stump speech, and convince as many potential voters as possible to vote for you. Unfortunately, there are only so many hours in a day, so you cannot go everywhere. You therefore have to plan your campaign trips carefully, trading off travel time, the time spent at each stop, and the number of voters you can sway. It is best to let a computer do the planning for you.

For each candidate campaign stop you are given the number of voters you expect to sway by appearing there and the number of hours you would have to spend at that location. In addition, for each ordered pair of stops you are given the travel time from one to the other. Given the total number of hours available, you can then plan an itinerary that sways as many voters as possible.

The tour always starts at city 1 and must return to city 1, but you do not have to campaign there — you may pass through it without spending its hours. Likewise, you may pass through any other city without campaigning; in that case you spend none of its hours and gain none of its voters.

The first line contains a number $K \ge 1$, the number of data sets in the file. It is followed by $K$ data sets of the following form.

The first line of each data set contains two numbers $n$ and $H$. Here $1 \le n \le 10$ is the number of candidate campaign stops, and $1.0 \le H \le 24.0$ is the number of hours you have available (this may be fractional).

This is followed by $n$ lines, each describing one campaign stop with two numbers: an integer $v_i \ge 0$ and a fractional number $h_i \ge 0$. $v_i$ is the number of voters you could sway at that stop, and $h_i$ is the number of hours you would have to spend there.

Finally, this is followed by $n$ more lines, each containing $n$ numbers, where the $j$-th number of line $i$ is the fractional travel time from city $i$ to city $j$. Thus the $i$-th number of line $i$ is $0$, but the travel time from city $i$ to city $j$ is not necessarily equal to the travel time from city $j$ to city $i$.

For each data set, first output “Data Set x:” on a line by itself, where $x$ is its number. Then output the maximum number of voters that can be swayed within the available time $H$. The tour always starts at city 1 and has to return there, although the candidate does not have to campaign there.