G. Go Go GPA
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Suppose that NTU has decided to revise the calculation of GPA. The new calculation method is explained as below.

  • For each semester, calculate the average original score, which is the weighted average score of all the courses one takes by credit.
  • For that semester, the semester GPA score is determined accordingly to the average original score as shown in the below table.
  • Finally, the final GPA score of one's university career is the non-weighted average semester GPA score from each semester.
Now, a freshman, Gareth, is about to study in NTUIM. Assume that NTUIM has $$$N$$$ required courses and the estimated score of each of the courses is $$$a_1, a_2, ..., a_N$$$ and the credits of each of them is $$$b_1, b_2, ..., b_N$$$ accordingly. Moreover, Gareth wishes to graduate in exactly $$$K$$$ semesters. The goal is to determine how many courses to take in each semester in order to maximize the final GPA score of his university career. However, for the $$$n$$$-th $$$(n \geq 2)$$$ course, "taking" the previous $$$n - 1$$$ courses are all prerequisites (it's fine to fail them). Nevertheless, one may take a course and its prerequisites in the same semester (e.g. one is allowed to take the sixth, the seventh, and the eighth courses in the same semester but is not allowed to take only the sixth and the eighth courses in that semester since he/she is required to take the seventh course in order to take the eighth course). Thus, one must take the courses in order but may take as many as they want in one semester. Please keep in mind that Gareth has to take at least one course in each semester and must finish all the courses in exactly $$$K$$$ semesters (Never mind if he failed the courses).
gradesemester GPA scoreaverage original score (round to the nearest integer)
A+4.390-100
A4.085-89
A-3.780-84
B+3.377-79
B3.073-76
B$$$-$$$2.770-72
C+2.367-69
C2.063-66
C-1.760-62
F00-59
Input

The first line contains one integer $$$N\,(1 \leq N \leq 100)$$$ — the number of required courses.

The second line contains $$$N$$$ integers $$$a_1, a_2, ..., a_N \, (0 \leq a_1, a_2, ..., a_N \leq 100)$$$ — the estimated scores of each courses in order.

The third line also contains $$$N$$$ integers $$$b_1, b_2, ..., b_N \, (1 \leq b_1, b_2, ..., b_N \leq 5)$$$ — the credits of each courses in order.

The fourth line contains one integer $$$K\,(1 \leq K \leq N)$$$ — the number of semesters.

Output

Output the highest possible final GPA score of Gareth's university career. Answers within $$$10^{-6}$$$ of the correct answer will be accepted as correct.

Examples
Input
3
70 80 75
3 1 4
2
Output
3.0000000
Input
6
30 95 65 75 55 80
1 1 1 1 1 1
3
Output
2.5666667
Note

For the first example, the best way to take the three courses in exactly two semesters is to take the first two courses in the first semester and take the third course in the second semester. Then, the average original score of the first semester is $$$\frac{70\times 3+80\times 1}{3+1} = 72.5$$$ and the average original score of the second semester is $$$\frac{75\times 4}{4} = 75$$$. Therefore, the semester GPA scores for the two semesters are both $$$3.0$$$. Finally, the final GPA score of his university career is the unweighted average of the two semester GPA scores, $$$\frac{3.0+3.0}{2} = 3.0$$$.