Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito tiene $N$ joyas. Cada joya tiene un valor $V_i$ y un peso $W_i$. Como Fito es una persona ahorrativa pero al mismo tiempo le gusta el lujo, el decidió regalarle a su novia solamente $K$ joyas de las $N$ existentes. Fito decidió mantener las joyas que combinadas fueran las más bellas. El valor de belleza combinada  de  un  conjunto $S = {i_1, i_2,…, i_k}$ de $K$ joyas se determina como:

Fito quiere seleccionar $K$ joyas tal que su belleza combinada sea máxima . Ayúdalo a hacer esto.

Input

La primera línea de la entrada contiene dos enteros positivos: $N$ – el número de joyas disponibles, y $K$ – el número de joyas que Fito quiere regalar $(1 \le K \le N \le 10^5)$.
Las siguientes $N$ líneas contienen cada una dos enteros – $V_i$ y $W_i$ $(0 \le Vi \le 10^6, 1 \le W_i \le 10^6)$. La suma de todos los $V_i$ y la suma de todos los $W_i$ no exceden $10^7$ (por separado).

Output

El mayor valor de belleza combinada de exactamente $K$ joyas con una precision de  $10^{-6}$.

Sample test(s)