Problem: A new lord assumed the position by the death of the previous lord in a Far Eastern province.

The new greedy lord hates concave polygons, because he believes they need much wasted area to be drawn on paper. He always wants to modify them to convex ones.

His castle is currently surrounded by a wall forming a concave polygon, when seen from the above. Of course he hates it. He believes more area could be obtained with a wall of a convex polygon. Thus he has ordered his vassals to have new walls built so they form a convex polygon.

Unfortunately, there is a limit in the budget. So it might be infeasible to have the new walls built completely. The vassals has found out that only up to r meters of walls in total can be built within the budget. In addition, the new walls must be built in such a way they connect the polygonal vertices of the present castle wall. It is impossible to build both of intersecting walls.

After long persuasion of the vassals, the new lord has reluctantly accepted that the new walls might not be built completely. However, the vassals still want to maximize the area enclosed with the present and new castle walls, so they can satisfy the lord as much as possible.

Your job is to write a program to calculate, for a given integer r, the maximum possible area of the castle with the new walls.



Input

The input file contains several test cases.

Each case begins with a line containing two positive integers n and r. n is the number of vertices of the concave polygon that describes the present castle wall, satisfying 5 ≤ n ≤ 64. r is the maximum total length of new castle walls feasible within the budget, satisfying 0 ≤ r ≤ 400.

The subsequent n lines are the x- and y-coordinates of the n vertices. The line segments (xi, yi) - (xi+1, yi+1) (1 ≤ i ≤ n - 1) and (xn, yn) - (x1, y1) form the present castle wall of the concave polygon. Those coordinates are given in meters and in the counterclockwise order of the vertices.

All coordinate values are integers between 0 and 100, inclusive. You can assume that the concave polygon is simple, that is, the present castle wall never crosses or touches itself.

The last test case is followed by a line containing two zeros.

Output

For each test case in the input, print the case number (beginning with 1) and the maximum possible area enclosed with the present and new castle walls. The area should be printed with exactly one fractional digit.

Example

Input

5 4
0 0
4 0
4 4
2 2
0 4
8 80
45 41
70 31
86 61
72 64
80 79
40 80
8 94
28 22
0 0


Output

case 1: 16.0
case 2: 3375.0

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 66;
const int M = 40000 + 10;
const int O = 20000 + 5;
const long double INF = 1e10;

int n, r;
int st, test;
int x[N], y[N];
int nx[N], ny[N];
bool ok[N][N];
long double f[N][M];

int sign(int x)
{
	return x < 0 ? -1 : x > 0;
}

int xmult(int p1, int p2, int q)
{
	return sign((x[p1] - x[q]) * (y[p2] - y[q]) - (x[p2] - x[q]) * (y[p1] - y[q]));
}

int on(int p1, int p2, int q)
{
	if (xmult(p1, p2, q)) return false;
	return (x[p1] - x[q]) * (x[p2] - x[q]) + (y[p1] - y[q]) * (y[p2] - y[q]) < 0;
}

int xmult(int p1, int p2)
{
	return x[p1] * y[p2] - x[p2] * y[p1];
}

int intersect(int p1, int p2, int q1, int q2)
{
	return xmult(p1, p2, q1) * xmult(p1, p2, q2) < 0 && xmult(q1, q2, p1) * xmult(q1, q2, p2) < 0;
}

void update(long double &a, long double b)
{
	if (a > b) a = b;
}

long double dis(int u, int v)
{
	return hypot(x[u] - x[v], y[u] - y[v]);
}

void solve()
{
	st = 0;
	for(int i = 0; i < n; ++ i) {
		cin >> x[i] >> y[i];
		if (x[i] < x[st]) {
			st = i;
		}
	}
	for(int i = 0; i < n; ++ i) {
		nx[i] = x[(i + st) % n];
		ny[i] = y[(i + st) % n];
	}
	for(int i = 0; i < n; ++ i) {
		x[i] = nx[i];
		y[i] = ny[i];
	}
	x[n] = x[0];
	y[n] = y[0];

	memset(ok, 0, sizeof ok);
	for(int i = 0; i < n; ++ i) {
		for(int j = i + 2; j <= n; ++ j) {
			if (i == 0 && j == n) continue;
			bool flag = true;
			{
				for(int k = 0; k < n; ++ k) {
					if (k == i || k == j % n) continue;
					if (on(i, j, k)) {
						flag = false;
						break;
					}
				}
			}
			if (flag) {
				for(int k = 0; k < n; ++ k) {
					if (intersect(i, j, k, k + 1)) {
						flag = false;
						break;
					}
				}
			}
			if (flag) {
				int area = xmult(i, j);
				for(int k = j - 1; k >= i; -- k) {
					area += xmult(k + 1, k);
				}
				if (area <= 0) flag = false;
			}
			ok[i][j] = flag;
		}
	}

	for(int i = 0; i <= n; ++ i) {
		for(int j = 0; j < M; ++ j) {
			f[i][j] = INF;
		}
	}
	f[0][O] = 0;

	for(int i = 0; i < n; ++ i) {
		for(int j = 0; j < M; ++ j) {
			if (f[i][j] >= INF) continue;
			update(f[i + 1][j + xmult(i, i + 1)], f[i][j]);
			for(int k = i + 2; k <= n; ++ k) {
				if (ok[i][k]) {
					update(f[k][j + xmult(i, k)], f[i][j] + dis(i, k));
				}
			}
		}
	}

	int ret = 0;
	for(int i = O; i < M; ++ i) {
		if (f[n][i] - 1e-8 > r) continue;
		ret = i - O;
	}
	if (ret & 1)
		printf("%d.5\n", ret >> 1);
	else
		printf("%d.0\n", ret >> 1);
}

int main()
{
	test = 0;
	for( ; cin >> n >> r && (n || r); ) {
		printf("case %d: ", ++ test);
		solve();
	}
	return 0;
}