Study Days

Interview

Time limit1sMemory limit128 MB

Summary

Distribute H study hours among n courses, each with 10 grade thresholds, to maximize the average grade point, rounded to two decimals.

Level: Medium5 of 10
Topics: Dynamic programming, Array, Implementation, Sorting
Solved: No attempts yet

Problem

To help you prepare for your final exams, the university gives you a limited number of study days. Because study time is scarce, you must divide it wisely among your courses to maximize your GPA.

Each course offers several grades, and each grade requires a minimum number of study hours. Spending more hours on a course can raise its grade. Sometimes it is worth accepting a low grade in one demanding course so that you can secure high grades in several other courses.

Given the number of study hours available and, for every course, how many hours are needed to earn each possible grade, compute the maximum GPA you can achieve.

Your GPA is the average of the grade points of your $n$ courses:

$\text{GPA} = \frac{1}{n}\sum_{i=1}^{n} p_i$

where $p_i$ is the grade point earned in course $i$ .

Input

The first line contains an integer $K \ge 1$ , the number of data sets. Each data set has the following form:

The first line contains two integers $n$ and $H$ : the number of courses ( $1 \le n \le 10$ ) and the number of study hours available ( $0 \le H \le 100$ ).
Each of the next $n$ lines contains 10 integers. The integers on line $i$ give, in order, the number of hours you must study course $i$ to earn each grade:

Grade	A	A-	B+	B	B-	C+	C	C-	D+	D
Points	4.0	3.7	3.3	3.0	2.7	2.3	2.0	1.7	1.3	1.0

The 10 integers on each line are non-increasing (earning an A requires the most hours). If you study at least the listed number of hours for a grade, you earn that grade; you always receive the best grade you can afford. If you do not study enough even for a D, the course grade is F, worth 0.0 points.

Output

For each data set, first print Data Set x: on its own line, where $x$ is the data set number (starting from 1). Then print the maximum GPA obtainable by distributing your $H$ study hours among the courses, rounded to two decimal places (round half up).

Examples3

Example 1

Input

1
3 60
40 37 35 33 30 26 20 10 5 1
10 10 10 10 10 10 10 10 10 1
24 23 22 21 20 20 20 20 20 20

Expected output

Data Set 1:
3.43

Example 2

Input

1
1 0
5 5 5 5 5 5 5 5 5 5

Expected output

Data Set 1:
0.00

Example 3

Input

1
2 100
10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1

Expected output

Data Set 1:
4.00