시험 공부 기간

기말고사를 준비할 수 있도록 학교에서 제한된 공부 기간을 준다. 공부할 시간이 부족하기 때문에, 평점(GPA) 을 최대로 만들려면 이 시간을 과목들에 잘 나누어 배분해야 한다.

각 과목에는 여러 학점이 있고, 학점마다 받기 위해 필요한 최소 공부 시간이 정해져 있다. 한 과목에 더 많은 시간을 투자하면 그 과목의 학점이 올라간다. 때로는 부담이 큰 한 과목에서 낮은 학점을 감수하고, 대신 다른 여러 과목에서 높은 학점을 확보하는 편이 유리할 수 있다.

사용할 수 있는 총 공부 시간과, 각 과목에서 학점별로 필요한 시간이 주어질 때, 얻을 수 있는 최대 평점을 구하라.

평점은 $n$개 과목의 학점 점수의 평균이다:

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

여기서 $p_i$는 $i$번째 과목에서 받은 학점의 점수이다.

첫 줄에 데이터 집합의 개수 $K \ge 1$ 이 주어진다. 각 데이터 집합의 형식은 다음과 같다.

• 첫 줄에 두 정수 $n$과 $H$가 주어진다. $n$은 수강 과목 수($1 \le n \le 10$), $H$는 사용할 수 있는 공부 시간($0 \le H \le 100$)이다.
• 이어서 $n$개의 줄에 각각 10개의 정수가 주어진다. $i$번째 줄의 정수들은 순서대로, $i$번째 과목에서 각 학점을 받기 위해 필요한 공부 시간을 나타낸다.

각 줄의 10개 정수는 증가하지 않는 순서로 주어진다(A를 받는 데 필요한 시간이 가장 크다). 어떤 학점에 필요한 시간 이상을 그 과목에 투자하면 그 학점을 받으며, 항상 얻을 수 있는 가장 높은 학점을 받는다. D를 받기에도 부족하게 공부하면 그 과목의 학점은 F(0.0점)가 된다.

각 데이터 집합에 대해 먼저 Data Set x: 를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호(1부터 시작)이다. 그다음, $H$시간의 공부 시간을 과목들에 나누어 얻을 수 있는 최대 평점을 소수점 둘째 자리까지 반올림하여 출력한다(경계값은 올림, round half up).