K Best

데미(Demy)는 $n$개의 보석을 가지고 있다. $i$번째 보석의 가치는 $v_i$, 무게는 $w_i$이다.

데미는 이 중 정확히 $k$개를 골라 그 비가치(specific value) 를 최대로 만들고자 한다. 고른 집합 $S = {i_1, i_2, \ldots, i_k}$의 비가치는 다음과 같이 정의된다.

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

크기가 $k$인 모든 부분집합에 대하여 비가치의 최댓값을 구하여라.

첫째 줄에 보석의 개수 $n$과 골라야 하는 개수 $k$가 주어진다 ($1 \le k \le n \le 100,000$).

다음 $n$개의 줄에는 각각 두 정수 $v_i$와 $w_i$가 주어진다 ($0 \le v_i \le 10^6$, $1 \le w_i \le 10^6$). $\sum v_i$와 $\sum w_i$는 모두 $10^7$ 이하이다.

비가치의 최댓값은 유리수이다. 이를 기약분수 p/q 형태로 출력한다. 여기서 $p \ge 0$, $q \ge 1$은 정수이며 $\gcd(p, q) = 1$이다. 분모는 항상 출력한다(예: 3/1). 값이 $0$이면 0/1을 출력한다.