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.