Have You Driven a Fjord Lately?

The western Scandinavian coastline contains many small inlets from the sea known as fjords. Fjords have very steep sides, so a coastal road must curve back and forth around them, which makes travel tedious. To cut down the distances that must be traveled, a series of bridges will be built across the fjords.

Bridges are assembled from pre-constructed units, each 1 meter long, so every bridge has an integer length in meters. Because of funding limits, the total length of all bridges that can be built is at most $m$ meters. For safety reasons each bridge can span at most one fjord.

Each fjord is modeled as two line segments connecting three points. The middle point is the innermost tip of the inlet, and the road follows the two segments from one outer point, around the tip, to the other outer point. Every fjord's tip angle is less than $180^\circ$.

A bridge over a fjord is a straight segment joining a point on one side of the fjord to a point on the other side; you may choose where it meets each side. Its length must be a whole number of meters. Building it removes the stretch of road between its two endpoints (the part that detoured around the tip) and replaces it with the bridge, so the road saved is (length of road removed) $-$ (length of the bridge). For example, if a bridge of length 10 meters is built that cuts off 30 meters of old road, a savings of 20 meters is realized.

Place the bridges so that the total length of road saved is as large as possible, without the total bridge length exceeding $m$.

Each test case consists of two lines. The first line contains two positive integers $n$ and $m$: the number of fjords and the maximum total bridge length (in meters). The next line contains $2n+1$ pairs of integer coordinates for the fjords, where the last coordinate of fjord $i$ is the first coordinate of fjord $i+1$.

All coordinates are in meters and lie between $-300000$ and $300000$. The maximum values of $n$ and $m$ are $50$ and $3000$, respectively.

The input consists of several test cases and ends with a line containing 0 0.

For each test case, print one line containing the case number, the total bridge length used, and the total road saved by the optimal placement of bridges, in the format shown below. All values are in meters, and the amount saved is rounded to the nearest hundredth.

Case X: L meters used saving S meters