Cramming Schedule

Time limit1sMemory limit1024 MB

Summary

Given exam deadlines, credits, and the study hours needed for each grade, find the highest credit-weighted grade point average when only one subject can be studied at a time.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Greedy
Solved: No attempts yet

Problem

Yumin has to take final exams for $N$ subjects this semester. Each subject's grade is one of 13 levels, from lowest to highest: F, D-, D0, D+, C-, C0, C+, B-, B0, B+, A-, A0, A+. Their grade points are 0.0, 0.7, 1.0, 1.3, 1.7, 2.0, 2.3, 2.7, 3.0, 3.3, 3.7, 4.0, and 4.3, respectively.

The exam for subject $i$ is $t_i$ hours from now, and its credit count is $c_i$ . To earn the $j$ -th lowest grade in that subject, Yumin must study it for at least $s_{i,j}$ hours. Each subject can be studied only until its exam time, and Yumin cannot study two subjects at the same time. Taking an exam takes no time, and several exams can be taken at the same time.

Yumin has not studied at all yet and wants to maximize the grade point average through efficient cramming. The grade point average is the sum, over all $N$ subjects, of each subject's credits times the grade point earned in it, divided by the total credits of the $N$ subjects. A subject with an F still counts toward the total credits.

Subject	Exam time	Credits	D-(0.7)	D0(1.0)	D+(1.3)	C-(1.7)	C0(2.0)	C+(2.3)	B-(2.7)	B0(3.0)	B+(3.3)	A-(3.7)	A0(4.0)	A+(4.3)
Calculus 1	30	4	3	7	10	14	16	20	27	30	60	88	120	200
World History	80	3	2	4	6	8	10	30	50	52	53	198	199	200
Mathematics 3	180	3	5	10	15	20	25	35	50	75	80	90	95	100
Information Science 3	200	3	1	1	1	1	1	1	1	1	1	1	1	2

For example, in the situation above, the best strategy is as follows.

Study Calculus 1 for 27 hours first.
Next, study World History for 3 hours.
Take the Calculus 1 exam. Having studied 27 hours in total, Yumin earns a B- (2.7).
Study World History for 50 more hours.
Take the World History exam. Having studied 53 hours in total, Yumin earns a B+ (3.3).
Study Mathematics 3 for 100 hours.
Take the Mathematics 3 exam. Having studied 100 hours in total, Yumin earns an A+ (4.3).
Of the 20 hours left before the Information Science 3 exam, study Information Science 3 for at least 2 hours.
Take the Information Science 3 exam. Having studied at least 2 hours in total, Yumin earns an A+ (4.3).

In this case, the grade point average is $\cfrac{4\times 2.7 + 3\times 3.3 + 3\times 4.3 + 3\times 4.3}{4+3+3+3} \approx 3.576923076923$ .

Input

The first line contains the number of subjects $N$ .

From the second line onward, the next $N$ lines describe the subjects. The $i$ -th line contains 15 integers $t_i, c_i, s_{i,1}, s_{i,2}, \cdots, s_{i,13}$ , separated by spaces.

Output

Print the maximum grade point average Yumin can earn. An absolute or relative error of up to $10^{-6}$ is allowed.

Constraints

$1 \leq N \leq 300$
$1 \leq t_i \leq 10^8$
$1 \leq c_i \leq 4$
$0 = s_{i,1} < s_{i,2} \leq s_{i,3} \leq \cdots \leq s_{i,13} \leq 10^8$

Examples1

Example 1

Input

4
30 4 0 3 7 10 14 16 20 27 30 60 88 120 200
80 3 0 2 4 6 8 10 30 50 52 53 198 199 200
180 3 0 5 10 15 20 25 35 50 75 80 90 95 100
200 3 0 1 1 1 1 1 1 1 1 1 1 1 2

Expected output

3.576923076923