Problem D
Drive Safely

CC0 via Pxhere

A new stretch of road has just been built from Askøy to Bergen. Before the road can be opened for the public, however, a decision needs to be made as for which speed limits to impose. The minister of transportation wants the travelling time from Askøy to Bergen to be as small as possible, but he also imposes some constraints:

• For safety reasons, the speed limit through a turn of $\alpha $ degrees can be at most $|180-\alpha |$ km/h. Even on a straight line, the speed limit can not exceed $180$ km/h.

• To save money on sign costs, the minister of transportation will only allow $k$ speed limit signs to be placed along the road.

The road is designed as a polyline, a sequence of $n$ coordinates: the road starts in the first location, follows a straight line to the second location, from there follows a straight line to the third location, and so forth, until reaching the final location. Note that the road might cross itself with bridges or tunnels, but there will not be any intersections where a car can take a shortcut.

The speed limit is initially $180$ km/h. Note that it is allowed to place two speed limit signs very close to each other, and the minister of transportation will allow speed limit signs to hold decimal values with infinite precision.

Input

The first line of input contains two positive integers $n$ ($2 \leq n \leq 200$), and $k$ ($1 \leq k \leq 50$). On each of the next $n$ lines follows the locations of the polyline describing the road, starting with where the road starts at Askøy, ending with where the road ends in Bergen. The $i^{\text {th}}$ location is described by two real numbers $x_ i$ and $y_ i$ ($-1\, 000\, 000 \leq x_ i, y_ i \leq 1\, 000\, 000$), denoting the coordinates in kilometers away from the arbitrarily chosen origin. All turns are at most $179$ degrees either clockwise or counterclockwise, and coordinates are given with at most $6$ digits after the decimal point.

Output

A single real number, the shortest possible travelling time from Askøy to Bergen (in hours). Any answer within an absolute or relative error of $10^{-6}$ will be accepted.

6 2
0.0 0.0
90.0 0.0
90.0 30.0
120.0 30.0
120.0 0.0
210.0 0.0

2.0