INBOX - India in Box

There is a well-known challenge in India. The challenge is as follows:

A merchant had some boxes. The boxes had weight and cost. He wants to give K boxes to one guy and the rest to other guy. Each guy has an average that is calculated by taking (Sum of Weights) / (Sum of Costs) of this guy. He wants to know what the smallest possible sum of the averages of the two guys he can achieve by making the distribution of the boxes.

Your task is to solve the challenge.

Input

The input contains several test cases. A test case begins with a line containing two integers N and K (1 <= K < N <= 100) representing the total number of boxes and the value of K, respectively. The next N lines contains two integers each, wi and ci (1 <= wi, ci <= 50), indicating the weight and cost of the ith box, respectively.

The last test case is followed by a line containing a single 0.

Output

For each test case, print a line containing a single value, the smallest possible sum of the averages, accurate to 5 decimal places.

Example

Input:
8 4
2 1
3 2
4 3
5 4
6 5
7 6
8 7
10 8
0 0

Output:
2.49845

Added by:Mateus Dantas [ UFCG ]
Date:2013-02-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Mateus Dantas

hide comments
2013-03-19 05:24:44 MarioYC
What is the number of test cases?

Nevermid, needed to optimize it. Nice problem!

Last edit: 2013-03-19 12:35:34
2013-02-24 05:17:42 Mateus Dantas [ UFCG ]
:) You hit the spot Alex Anderson!
2013-02-23 21:40:14 Alex Anderson
Excellent!
2013-02-23 03:32:12 Alex Anderson
=/ Current algo's runtime is on the order of 1billion operations per test case = no good.
2013-02-21 09:07:56 Ehor Nechiporenko
Hart task!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.