Marisa loves collecting stuff. In front of her, there are n items, where the i-th item has a weight of wi and a value of vi. She wants to take all of them home, but they are too heavy. Therefore, she decides to only take k items.
If she takes k items, the value of these items is given by:
v1+v2+...+vkw1+w2+...+wk
Help Marisa choose items so that the achieved value is maximized.
### Input
- The first line contains two integers n,k.
- The next n lines, each line contains two integers vi and wi.
### Output
- Print a real number, the maximum achievable value. The answer is considered correct if the difference from the correct answer is not greater than 10−3.
### Constraints
- 1≤k≤n≤105.
- 1≤vi,wi≤109.
### Example
Input:
531322254214
Output:
1.0000000000
