Rig Placement

Once we’ve found where the oil is (and — beyond what you solved in the previous question — also how much oil there is in different places), the next question is where to place oil rigs so that after the rig explodes, we can spill as much oil as possible. This is actually not completely trivial.

We can model the problem as follows: There are 1 ≤ n ≤ 100 oil fields we may want to exploit. For each of the oil fields, we can decide how much money to invest in that oil field, in increments of million dollars, from 0–m. (m is the maximum investment per oil field.) For each oil field 1 ≤ i ≤ n, and each amount of money j ∈ {0, 1, 2,... ,m}, a table a[i,j] of non-negative real numbers tells us how much oil we will get. The table entries are non-decreasing in j (more money means at least as much oil as before), but other than that, they may be arbitrary. The total budget available for rigs is an integer 0 ≤ B ≤ 100 (again, in increments of millions of dollars). You are to calculate the maximum total amount of oil you can extract with your budget.

The first line is the number K of input data sets, followed by the K data sets, each of the following form:

The first line contains three integers n,m,B, the number of oil fields, the maximum investment per oil field, and the total budget.

This is followed by n lines, each consisting of m + 1 non-negative floating point numers, where the jth number is the amount of oil you would extract from the ith oil field if you invested j million dollars in it.

For each data set, output “Data Set x:” on a line by itself, where x is its number. On the next line, output the maximum total amount of oil you can extract from the oil fields together under the given constraints, rounded to two decimals. Each data set should be followed by a blank line.