题目描述

Anton, as a teacher at school, is organizing a disco for the children. He has been tasked with selecting a playlist so that everyone is thrilled with the celebration. But Anton has a huge database of songs, and unfortunately, the time for the disco is limited :(.

Specifically, there are $n$ songs in the database. Each song can be characterized by two integers $t_i$ and $r_i$ --- the length of the song and its rating. As a music lover, Anton wants to select $\textbf{exactly}$ $k$ songs (i.e., not fewer) to maximize the ratio of the sum of ratings to the sum of lengths.

More formally, let $S$ be the set of songs and $X \subseteq S$, $|X|=k$ --- a subset of songs that have been selected for the playlist. The goal is to maximize $\displaystyle \frac{\sum_{i \in X} r_i}{\sum_{i \in X} t_i}$. In other words, it is necessary to find the sum of the numbers $r_i$ of all the songs that will be played at the disco, find the sum of the numbers $t_i$ of all the songs that will be played at the disco, and divide the former by the latter. This number needs to be maximized.

Find and output the maximum possible ratio.

输入格式

The first line contains two integers $n$, $k$ ($1 \le k \le n \le 10^5$) --- the total number of songs and the number of songs to be selected for the playlist.

The second line contains $n$ integers $r_i$ ($1 \le r_i \le 10^5$).

The third line contains $n$ integers $t_i$ ($1 \le t_i \le 10^5$).

输出格式

Output a single number --- the maximum ratio.

Your answer will be considered correct if its absolute or relative error does not exceed $10^{-4}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer will be accepted if and only if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$.

2 2
1 2
2 3

0.600000

5 2
1 2 3 2 3
2 4 2 5 3

1.200000

提示

In the first example, there are two songs that need to be added to the playlist. Therefore, the ratio will be:

$$\frac{1+2}{2+3}=\frac{3}{5}=0.6$$

In the second example, it is best to take the third and fifth songs. Therefore, the ratio will be:

$$\frac{3+3}{2+3}=\frac{6}{5}=1.2$$