Roof Construction

An architect wants to revise a roof profile designed by a designer so that rain and snow can slide off a convex shape.

The N input points are reference points of the original roof design. Treat the new roof as one polygonal chain drawn over the x-coordinate range of those points. Because the roof is the upper boundary of a convex polygon, the slopes of its segments must not increase from left to right. The roof may contain at most K line segments.

Every input point must lie on or below the new roof. For a point (x, y), let R(x) be the y-coordinate of the new roof at the same x-coordinate. The difference at that point is R(x) - y, and the total difference is the maximum of that value over all input points.

Given the points and K, compute the minimum possible total difference.

The first line contains the number of points N and the maximum number of segments K. (1 <= N <= 100, 1 <= K <= N)

Each of the next N lines contains the coordinates x and y of one point. Both x and y are decimal numbers between 0 and 10000, inclusive.

Print the minimum possible total difference, rounded to three digits after the decimal point.