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, w_i and c_i (1 ≤ w_i, c_i ≤ 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

Output:
2.49845