27654번 - 시험 스페셜 저지

문제

$N$개의 시험 성적이 주어진다. 이 중 $i$번째 성적은 $Q_i$개의 문제 중 $P_i$개를 맞혔다고 표현된다.

다음과 같이 집합 $X$의 평균 성적을 정의하자.

$${ {\sum P_x}\over{\sum Q_x} } \hspace{1em}(x\in{X}, X \subset{} \left\{1,2, \cdots{}, N \right\} )$$

집합 $X$의 크기 $K$가 주어질 때, 집합 $X$의 평균 성적의 최댓값을 구하여라. 즉, $N$개의 시험에서 $K$개의 시험을 적절히 뽑아 평균 성적을 최대화하는 것이 목표이다.

입력

첫째 줄에 전체 시험의 개수를 나타내는 정수 $N$과 집합 $X$의 크기를 나타내는 정수 $K$가 주어진다. $(1 \le{} K \le{} N \le{}100,000円)$

둘째 줄부터 $N$개의 줄에 걸쳐 각 시험에 대한 정보 $P_i$와 $Q_i$가 순서대로 주어진다. $(0 \le{} P_i \le{} 100,000,円 1 \le{} Q_i \le{} 100,000,円 P_i \le{} Q_i)$

출력

집합 $X$의 평균 성적의 최댓값을 출력한다. 정답과의 상대/절대 오차가 10ドル^{-6}$ 이하인 경우 정답으로 인정된다.

제한

힌트