Grades

Peter is reviewing his midterm grades—something seems off. He needs to improve a few subjects, but time is limited… He has to plan his improvements: which subjects to focus on, what grades to aim for, and how much time to allocate to each.

He thinks as follows: “I have $N$ subjects, I know my current grades ( $g_{1},\ldots,g_{N}$ ), and I have $T$ time units to prepare. I also know how much time I need to improve in subject $i$ from a grade of 1 to 2, from 2 to 3, from 3 to 4, or from 4 to 5 ( $t_{i,1},t_{i,2},t_{i,3},t_{i,4}$ ). Naturally, if I want to improve from 2 to 4 in subject $i$ , I need $t_{i,2}+t_{i,3}$ time to prepare. I absolutely don’t want to fail any subjects, so I must improve all grades of 1. Within the given time limit $T$ , what is the best average grade I can achieve?”

Let’s help him answer this question!

Example:

N=2
current grades: 1, 2
T=20
the needed preparing times:
1. subject: 8 8 9 10
2. subject: 2 3 4 5
He has two choices:
- Improve in the 1. subject to 2, and devote the remaining to the 2. subject
    This way 8+(3+4+5) time units used, and the average is 3.5.
- Improve to 3 in each subjects.
    This way (8+8)+3 time units used, and the average is 3.0.

Input specification

The first line contains the number of subjects, $N$ . The second line lists the current grades, $g_{1},\ldots,g_{N}$ . The third line contains the available time, $T$ . The following $N$ lines each contain the times required for improvement, $t_{i,1}\le \ldots \le t_{i,4}\ \ i=1,\ldots ,N$ The numbers on each line are separated by spaces.

Output specification

If it is possible to improve all grades to at least a 2, output the best achievable average rounded to 2 decimal places on a single line. Otherwise, output the string :-( on a single line.