수강 철회

문제 정보

문제

이번 학기에 욕심을 부려 학점 초과신청을 한 백준이는 중간고사 성적을 보고 한숨을 토할 수밖에 없었습니다. 다음 학기 장학금을 받을 만큼 성적이 잘 나오지 않았기 때문입니다. 이제 백준이에게 남은 희망은 다음 주의 수강 철회 기간 뿐입니다.

백준이네 학교에서는 장학금을 학생의 중간고사 등수와 기말고사 등수에 따라 배정합니다. 어떤 학생이 듣는 i번째 과목의 수강생 수가 c_{i}라고 합시다. 그리고 이 학생의 i번째 과목 중간 고사 등수가 r_{i}라고 하면, 이 학생의 중간 고사 누적 등수 cumulativeRank 는 다음과 같이 정의됩니다.

cumulativeRank = sum(r_{i}) / sum(c_{i})

예를 들어 백준이가 수강생이 각각 150, 200, 15명인 3개의 과목을 듣는데, 각각 100, 10, 5등을 했다면 백준이의 누적 등수를 다음과 같이 계산할 수 있지요.

(100 + 10 + 5) / (150 + 200 + 15) = 115 / 365 = 0.315..

수강 철회를 하면 철회한 과목은 중간 고사의 누적 등수 계산에 들어가지 않게 됩니다. 다행히 백준이네 학교에서는 수강 철회를 해도 남은 과목이 k 개 이상이라면 장학금을 받을 수 있습니다. 백준이가 적절히 과목을 철회했을 때 얻을 수 있는 최소 누적 등수를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 T (T <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 백준이가 수강하는 과목의 수 n(1 <= n <= 1,000)과 남겨둬야 할 과목의 수 k(1 <= k <= n)가 주어집니다. 다음 줄에는 n 개의 정수 쌍 (r_{i},c_{i}) 이 순서대로 주어집니다. (1 <= r_{i} <= c_{i} <= 1,000)

출력

각 줄마다 백준이가 얻을 수 있는 최소의 누적 등수를 출력합니다. 정답과 10{-7} 이하의 오차가 있는 답은 정답으로 인정됩니다.

예제 입력

3
3 2
1 4 6 10 10 17
4 2
4 8 9 12 3 10 2 5
10 5
70 180 192 192 1 20 10 200 6 102 60 1000 4 9 1 12 8 127 100 700

예제 출력

0.5000000000 
0.3333333333 
0.0563991323

노트

6개의 댓글이 있습니다.