Description

As EVs become more common, charging queues at highway rest stops keep getting longer. Along a quiet highway, rest stops are lined up in a straight line, each given as a distance (km) from the starting point (0km). The budget is tight, so you can install exactly C chargers. If the chargers cluster together, the far stretches of the highway become inconvenient to charge at. So you want to pick rest stops so that the "distance between the two closest chargers" is **as large as possible**. Find the maximum possible value of that minimum distance between adjacent chargers.

Input

Output

Constraints

• •2 ≤ C ≤ N ≤ 200,000
• •0 ≤ rest stop position ≤ 1,000,000,000 (all distinct integers)
• •Rest stop positions may not be given in sorted order

Examples

6 3
3 6 12 17 25 30

13