11351135 SUSTech Online Judge
Problem 1135 --Save Joy[Hard]

1135: Save Joy[Hard]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 971  Solved: 230
[Submit][Status][Web Board]

Description

Joy is now applying for postgraduate programs. But due to his low GPA, no school really wants to receive him. One day poor Joy meet Aladdin, Aladdin promises to help him delete some of his courses he attended to increase his GPA. But now he is confused again, can you write a program to help him point out the maximum GPA he can get by deleting courses.

It should be mentioned that the calculation formula of GPA is Σ(s[i]*c[i])/Σ(s[i])

, where the academic credit of the i-th course is s[i] and the score of the i-th course is c[i]. And because of the limitation of power of the magic lamp, he could at most delete k courses.

Input

The input contains multiple test cases. For each test case:

The first line has two positive integers n (1<=n<=105), k (0<=k<n), which is the total course number selected by Joy and the maximum number of deleting courses. The second line has n positive integers s[i]. The third line has n positive integers c[i] (1<=s[i], c[i]<=103).

Output

Output the highest final score. The answer should be round to 3 decimal places.


Sample Input

3 1
1 2 3
3 2 1

Sample Output

2.333

HINT

Source

 

[Submit][Status]