Антон, як вчитель в школі, організовує дискотеку для дітей. Йому було доручено вибрати музикальний плейлист такий, щоб всі були в захваті від свята. Але в Антона величезна база пісень, а час дискотеки, на жаль, обмежений :(.

А саме, у базі є $n$ пісень. Кожну пісню можна схарактеризувати двома цілими числами $t_i$ і $r_i$ --- довжина пісні, та її рейтинг. Антон, як меломан, хоче вибрати \textbf{рівно} $k$ пісень (тобто, не можна вибрати менше), щоб максимізувати відношення суми рейтингу до суми довжин. 

Більш формально, нехай $S$ --- множина пісень і $X \subseteq S$, $|X|=k$ --- підмножина пісень, яка була вибрана в плейлист. Треба максимізувати $\displaystyle \frac{\sum_{i \in X} r_i}{\sum_{i \in X} t_i}$. Тобто, потрібно знайти суму чисел $r_i$ всіх пісень, які будуть грати на дискотеці, знайти суму чисел $t_i$ всіх пісень, які будуть грати на дискотеці, та поділити перше на друге. Ось це число потрібно максимізувати.

Знайдіть та виведіть максимально можливе відношення.