K Best

Demy has $n$ jewels. The $i$-th jewel has value $v_i$ and weight $w_i$.

She wants to keep exactly $k$ of them so that their specific value is as large as possible. For a chosen set $S = {i_1, i_2, \ldots, i_k}$ the specific value is defined as

$$s(S) = \frac{\sum_{j=1}^{k} v_{i_j}}{\sum_{j=1}^{k} w_{i_j}}.$$

Determine the maximum possible specific value over all subsets of size $k$.

The first line contains two integers $n$ and $k$ — the number of jewels and the number to keep ($1 \le k \le n \le 100,000$).

Each of the next $n$ lines contains two integers $v_i$ and $w_i$ ($0 \le v_i \le 10^6$, $1 \le w_i \le 10^6$). Both $\sum v_i$ and $\sum w_i$ are at most $10^7$.

The maximum specific value is a rational number. Output it as an irreducible fraction p/q, where $p \ge 0$ and $q \ge 1$ are integers with $\gcd(p, q) = 1$. Always print the denominator (for example 3/1). If the value is $0$, print 0/1.