Light Aircraft

The light aircraft Eagle wants to travel from the starting point S to the destination T as quickly as possible. A larger fuel tank reduces the number of times the aircraft must land for refueling, but its weight may hurt speed and stability. A smaller tank can make the aircraft faster, but it may require more refueling stops.

Find the minimum fuel tank capacity needed to travel from S to T while landing at intermediate refueling airfields at most k times.

In a situation like the figure, if at most k = 2 intermediate landings are allowed, some routes may require a very large tank because one of their later flight segments is too long. The goal is to minimize the maximum fuel required by any single flight segment while staying within the allowed number of intermediate landings.

The following rules apply.

1. Every aircraft flies in a straight line between two points. Distances are measured in km and fuel is measured in L. The aircraft can fly 10km per 1L of fuel, and fuel is filled in whole-liter units.
2. The distance between two positions is the Euclidean distance on the plane. For instance, if g = (2, 1) and h = (37, 43), then d(g, h) is \(\sqrt{(2-37)^2 + (1-43)^2}\) = 54.671... . Since 50 < d(g, h) <= 60, that segment needs 6L of fuel.
3. The starting point S is always (0, 0), and the destination T is always (10000, 10000).
4. The number n of airfields excluding S and T satisfies 3 <= n <= 1000. Each airfield coordinate (x, y) consists of integers with 0 < x, y < 10000. The maximum allowed number k of intermediate refueling stops satisfies 0 <= k <= 1000.

The first line contains the number of airfields n and the maximum allowed number of intermediate refueling stops k, separated by a space.

Each of the next n lines contains the integer coordinates x y of one airfield.

Print the minimum integer fuel tank capacity that allows the aircraft to travel from S to T with at most k intermediate refueling stops.