피오르에 다리 놓기

서쪽 스칸디나비아 해안에는 바다에서 육지 안쪽으로 길게 들어온 좁은 만인 피오르가 많다. 피오르는 양쪽 절벽이 매우 가팔라서, 해안을 따라 난 도로는 피오르를 빙 돌아가야 하므로 이동 거리가 길어진다. 이를 줄이기 위해 피오르를 가로지르는 다리를 놓아 우회 거리를 단축하려고 한다.

다리는 길이가 각각 1미터인 미리 만들어 둔 단위 부품으로 조립하므로, 각 다리의 길이는 항상 정수(미터)이다. 예산 때문에 놓을 수 있는 다리 길이의 총합은 $m$미터를 넘을 수 없다. 안전상의 이유로 하나의 다리는 최대 하나의 피오르만 가로지를 수 있다.

각 피오르는 세 점을 잇는 두 선분으로 나타낸다. 가운데 점이 만의 가장 안쪽(꼭짓점)이고, 도로는 한쪽 바깥 점에서 이 꼭짓점을 지나 반대쪽 바깥 점까지 두 선분을 따라 이어진다. 모든 피오르의 꼭짓점 각도는 $180^\circ$ 미만이다.

한 피오르에 놓는 다리는 그 피오르의 두 변 위의 한 점과 다른 한 점을 잇는 곧은 선분이며, 각 변의 어느 지점에 닿게 할지 자유롭게 정할 수 있다. 다리의 길이는 정수여야 한다. 다리를 놓으면 두 끝점 사이의 도로(꼭짓점을 돌아가던 부분)가 다리로 대체되므로, 절약되는 거리는 (없어진 도로의 길이) $-$ (다리의 길이)이다. 예를 들어 길이 10미터의 다리로 30미터의 옛 도로를 없애면 20미터가 절약된다.

다리 길이 총합이 $m$을 넘지 않는 범위에서, 절약되는 도로 길이의 합이 최대가 되도록 다리를 놓아라.

각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 피오르의 개수 $n$과 놓을 수 있는 다리 길이의 최댓값 $m$(미터)이 양의 정수로 주어진다. 다음 줄에는 피오르들을 나타내는 $2n+1$개의 정수 좌표쌍이 주어지며, 피오르 $i$의 마지막 좌표가 피오르 $i+1$의 첫 좌표가 된다.

모든 좌표는 미터 단위이며 $-300000$ 이상 $300000$ 이하의 정수이다. $n$의 최댓값은 $50$, $m$의 최댓값은 $3000$이다.

입력은 여러 개의 테스트 케이스로 이루어지며, 0 0인 줄로 끝난다.

각 테스트 케이스마다 한 줄에 케이스 번호, 사용한 다리 길이의 총합, 그리고 최적으로 다리를 놓았을 때 절약되는 도로 길이의 총합을 아래 형식으로 출력한다. 모든 값의 단위는 미터이며, 절약되는 거리는 소수 둘째 자리까지 반올림하여 출력한다.

Case X: L meters used saving S meters