Flea King's Water Problem

In the land of fleas, there are \(n\) cities. The great flea king lives in the capital, which is city \(1\). Each city has a cylindrical water tank of unlimited height. After a rainy day, the \(i\)-th city collects water up to height \(h_i\). Due to geographical and meteorological factors, every two cities collect different heights of water.

The flea king has built an elaborate underground connection system. In each use of this system, he can choose an arbitrary set of cities. The water in all the selected water tanks will be connected for a sufficient time so that by the principles of connectivity, they equalize to the average of their current water heights. The new water height becomes \[ L = \frac{h_{i_1} + h_{i_2} + \cdots + h_{i_m}}{m}, \] where \(\{i_1, i_2, \ldots, i_m\}\) is the set of chosen cities. Due to the complexity of the system, the king can use this underground connection at most \(k\) times.

Your task is to determine the maximum possible water level in the capital (city \(1\)) after at most \(k\) operations. Note that in each operation the king may choose a new set of cities. One optimal strategy is to gradually upgrade the water level in the capital by connecting it with other cities that currently have higher water levels, starting with the smallest such candidate to maximize the final average.

inputFormat

The input consists of two lines:

• The first line contains two integers \(n\) and \(k\) \( (1 \leq n \leq 10^5, 0 \leq k \leq n)\), representing the number of cities and the maximum number of operations.
• The second line contains \(n\) distinct integers \(h_1, h_2, \dots, h_n\) \((1 \leq h_i \leq 10^9)\), representing the water heights collected by each city. Note that city \(1\) is the capital.

outputFormat

Output a single number: the maximum water level that the capital (city \(1\)) can achieve after performing at most \(k\) operations. The answer will be accepted if it has an absolute or relative error of at most \(10^{-6}\).

sample

2 1
1 2

1.5