Problem: You are a programmer working for your local city hall. The town you live in has a thriving tourism industry, especially the beaches on the shores of remote islands. The area around this island is composed of sandy beaches, but in recent years the area of ​​the sandy beaches has decreased due to coastal erosion. The Tourism Division, which took the situation seriously, asked you to simulate the shape change of the beach.

In the simulation, the shape of the beach after a certain period of time is obtained based on the current shape of the beach. For simplicity, the shape of the island's coastline is considered polygonal (not necessarily convex). During the period, it is assumed that the beach is eroded by R at a distance from the current coastline in Manhattan and sinks into the sea. Here, the Manhattan distance is the sum of the difference between the x-coordinates and the difference between the y-coordinates. That is, the Manhattan distance between (x1, y1) and (x2, y2) is given by | x1 --x2 | + | y1 --y2 |.

Your job is to write a program to find the length of the shoreline obtained as a result of the simulation from the shoreline of the sandy beach given as input. If an island is divided into two or more due to coastal erosion, find the length of the coastline for each divided island and output the sum of them.

It should be noted that the two line segments included in the coastline are parallel and the Manhattan distance is not exactly 2R.

Input

The input consists of multiple datasets. Each dataset is given in the following format.

> N R
> x1 y1
> x2 y2
> ...
> xN yN

The first line gives two non-negative integers N (3 ≤ N ≤ 100) and R (0 <R ≤ 100). These integers represent the number of vertices on the coastline and the distance eroded, respectively. In the following N lines, vertex information is given to each line, one for each line. Vertex information is given by two integers xi, yi (-10000 ≤ xi, yi ≤ 10000). The coordinates (xi, yi) represent the coordinates of the i-th vertex of the coastline, respectively. The coordinates of the vertices of the island are always given counterclockwise.

The end of the input is indicated by a single line containing two zeros separated by blanks.

Output

Output the length of the eroded coastline for each dataset. If the island is completely eroded and disappears, the length of the coastline should be treated as 0.0. The output value may contain an error of 0.01 or less. In addition, the value may be displayed in any number of digits after the decimal point.

Sample Input


3 1
0 0
10 0
5 10
3 1
0 0
10 0
0 10
4 1
0 0
10 0
10 10
0 10
0 0


Output for the Sample Input


22.6524758425
23.8994949366
32.0000000000






Example

Input

3 1
0 0
10 0
5 10
3 1
0 0
10 0
0 10
4 1
0 0
10 0
10 10
0 10
0 0


Output

22.6524758425
23.8994949366
32.0000000000

Solution (in CPP):

Solution:
#include<cstdio>
#include<complex>
#include<vector>
#include<cmath>
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

//FILE *fp=fopen("ShoreErosion_visu2.htm","w");
//FILE *fp=stderr;
FILE *fp=fopen("ShoreErosion_myans.txt","w");
typedef double Real;

typedef complex<Real> Point;
typedef complex<Real> Vector;
typedef pair<Point,Point> Segment;
typedef pair<Point,Point> Line;
typedef vector<Point> Polygon;

const Real eps=1e-9;
const Real PI=acos(-1.0);

template<class T> bool eq(T a,T b){
	return abs(a-b)<eps;
}
template<class T> int sgn(T a){
	if(eq(a,(Real)0.0)) return 0;
	if(a>0) return 1;
	return -1;
}

Real arg(Point p){
	return atan2(p.imag(),p.real());
}

Real crP(Vector a,Vector b){
	return (conj(a)*b).imag();
}

Real doP(Vector a,Vector b){
	return (conj(a)*b).real();
}

Point iLL(Line l1,Line l2){
	if(sgn(crP(l1.second-l1.first,l2.second-l2.first))==0) return Point(NAN,NAN);
	Point a=l1.first,b=l1.second;
	Point c=l2.first,d=l2.second;
	Real num=crP(c-a,d-a);
	Real den=crP(b-a,d-c);
	return a+(b-a)*num/den;
}

bool onSeg(Point a,Point b,Point c){
	return eq(abs(a-b),abs(a-c)+abs(c-b));
}

bool isPara(Segment s1,Segment s2){
	return sgn(crP(s1.second-s1.first,s2.second-s2.first))==0;
}

bool cmp_lex(const Point &p1,const Point &p2){
	if(sgn(p1.real()-p2.real())!=0){
		if(p1.real()<p2.real()) return true;
		return false;
	}
	return p1.imag()<p2.imag();
}

bool mergeIfAble(Segment &s,Segment t){
	if(sgn(crP(t.first-s.first,s.second-s.first))!=0) return false;
	if(sgn(crP(t.second-s.first,s.second-s.first))!=0) return false;
/*	Point pts[]={t.first,t.second};
	for(int i=0;i<2;i++){
		if(onSeg(s.first,pts[i],s.second)){
			s.second=pts[i];
		}else if(onSeg(s.second,pts[i],s.first)){
			s.first=pts[i];
		}
	}*/
	if(cmp_lex(s.first,s.second)==false) swap(s.first,s.second);
	if(cmp_lex(t.first,t.second)==false) swap(t.first,t.second);
	Segment res=s;
	if(cmp_lex(res.first,t.first)==false) swap(res,t);
	if(cmp_lex(res.second,t.first)==false){
		if(cmp_lex(res.second,t.second)) res.second=t.second;
		s=res;
		return true;
	}
	return false;
}
void mergeSegments(vector<Segment> &segs){
	while(true){
	bool flg=false;
	for(int i=0;i<segs.size();i++){
		for(int j=i+1;j<segs.size();j++){
			if(mergeIfAble(segs[i],segs[j])){
				segs[j--]=segs.back();
				segs.pop_back();
				flg=true;
			}
		}
	}
	if(flg==false) break;
	}
}

struct Segment2:Segment{
	vector<Point> pts;
	Segment2(){}
	Segment2(Segment s):Segment(s){}
};

vector<Segment> segs;
vector<Segment2> segs2;

Polygon poly;
Real R;

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
Vector dir[4];

void put(Segment seg){
	Point p=seg.first,q=seg.second;
	Real dx=abs((p-q).real()),dy=abs((p-q).imag());
	int rem=dx<dy?0:1;
	for(int i=0;i<4;i++){
		if(i%2!=rem) continue;
		Point p2=p+Point(::dx[i],::dy[i])*R;
		Point q2=q+Point(::dx[i],::dy[i])*R;
		int s=sgn(crP(q-p,q2-q));
		if(s<0) continue;
		segs.push_back(Segment(p2,q2));
	}
}

void put(Point p){
	for(int i=0;i<4;i++){
		int j=(i+1)%4;
		Point a=p+dir[i]*R;
		Point b=p+dir[j]*R;
		segs.push_back(Segment(a,b));
	}
}

Real mDis(Point a,Point b){
	return abs((a-b).real())+abs((a-b).imag());
}

Real mDis(Segment seg,Point p){
	if(onSeg(seg.first,seg.second,p)) return 0;
	Real res=min(mDis(seg.first,p),mDis(seg.second,p));
	for(int i=0;i<2;i++){
		Point q=p+dir[i];
		if(sgn(crP(q-p,seg.second-seg.first))==0) continue;
		Point r=iLL(Segment(p,q),seg);
		if(onSeg(seg.first,seg.second,r)){
			res=min(res,mDis(p,r));
		}
	}
	return res;
}

bool isin(Polygon poly,Point pt){/*ONは判定していない*/
	bool in=false;
	for(int i=0;i<poly.size();i++){
		Point a=poly[i],b=poly[(i+1)%poly.size()];
		a-=pt,b-=pt;
		if(sgn(a.imag()-b.imag())>0) swap(a,b);
		if(sgn(a.imag())<=0&&0<sgn(b.imag())){
			if(sgn(crP(a,b))<0) in=!in;
		}
	}
	return in;
}

Point center;
bool cmp(const Point &p1,const Point &p2){
	if(sgn(doP(p1-center,p2-center))<0) fprintf(stderr,"direction not correct\n");
	return sgn(abs(p1-center)-abs(p2-center))<0;
}

void showP(Point p){
	printf("(%f,%f) ",p.real(),p.imag());
}

vector<Segment> vec;

Real solve(){
	for(int i=0;i<4;i++) dir[i]=Vector(dx[i],dy[i]);
	for(int i=0;i<poly.size();i++){
		put(poly[i]);
	}
	for(int i=0;i<poly.size();i++){
		Point p=poly[i];
		Point q=poly[(i+1)%poly.size()];
		put(Segment(p,q));
	}
/*	for(int i=0;i<poly.size();i++){
		Point p=poly[i];
		for(int j=0;j<4;j++){
			Point q=p+dir[j]*R;
			segs.push_back(Segment(p,q));
		}
	}*/
	mergeSegments(segs);
	for(int i=0;i<segs.size();i++){
		segs2.push_back(Segment2(segs[i]));
	}
/*	for(int i=0;i<segs2.size();i++) for(int j=i+1;j<segs2.size();j++){
		Point a=segs2[i].first,b=segs2[i].second;
		Point c=segs2[j].first,d=segs2[j].second;
	//	if(sgn(crP(b-a,d-c))==0&&sgn(crP(c-a,b-a))==0){
	//		showP(a);showP(b);showP(c);showP(d);
	//		printf("\n");
	//	}
	}*/
	for(int i=0;i<segs2.size();i++) for(int j=i+1;j<segs2.size();j++){
		Segment2 &s1=segs2[i],&s2=segs2[j];
		Point p=iLL(s1,s2);
		if(isnan(p.real())) continue;
		if((!onSeg(s1.first,s1.second,p))||(!onSeg(s2.first,s2.second,p))) continue;
		s1.pts.push_back(p);
		s2.pts.push_back(p);
	}
	for(int i=0;i<segs2.size();i++){
		for(int j=0;j<poly.size();j++){
			Segment edge=Segment(poly[j],poly[(j+1)%poly.size()]);
			Point p=iLL(segs2[i],edge);
			if(isnan(p.real())) continue;
			if((!onSeg(segs2[i].first,segs2[i].second,p))||(!onSeg(edge.first,edge.second,p))){
				continue;
			}
			segs2[i].pts.push_back(p);
		}
	}
	for(int i=0;i<segs2.size();i++){
	//	segs2[i].pts.push_back(segs2[i].first);
	//	segs2[i].pts.push_back(segs2[i].second);
		for(int j=0;j<poly.size();j++){
			for(int k=0;k<4;k++){
				Point p=poly[j]+dir[k]*R;
				if(onSeg(segs2[i].first,segs2[i].second,p)){
					segs2[i].pts.push_back(p);
				}
			}
			Point p=poly[j];
			if(onSeg(segs2[i].first,segs2[i].second,p)){
				segs2[i].pts.push_back(poly[j]);
			}
		}
		center=segs2[i].first;
		sort(segs2[i].pts.begin(),segs2[i].pts.end(),cmp);
		if(!eq(segs2[i].pts.back(),segs2[i].second)) fprintf(stderr,"c\n");
	}
	Real res=0;
	for(int i=0;i<segs2.size();i++){
		for(int j=0;j+1<segs2[i].pts.size();j++){
			Point a=segs2[i].pts[j],b=segs2[i].pts[j+1];
			if(eq(a,b)) continue;
			Point mid=(a+b)/(Real)2.0;
			bool in=isin(poly,mid);
			if(!in) continue;
			bool suc=true;
			for(int k=0;k<poly.size();k++){
				Segment s=Segment(poly[k],poly[(k+1)%poly.size()]);
				Real dis=mDis(s,mid);
				if(sgn(dis-R)<0) suc=false;
			}
			if(!suc) continue;
			bool flg[2]={true,true};
			for(int k=0;k<poly.size();k++){
				Real dis1=mDis(a,poly[k]),dis2=mDis(b,poly[k]);
				if(sgn(dis1-R)<0||sgn(dis2-R)<0) fprintf(stderr,"a\n");
				if(eq(dis1,R)&&eq(dis2,R)){
					Point p=poly[k];
					int s=sgn(crP(b-a,p-a));
					int id=s==-1?0:1;
					flg[id]=false;
				}
			}
			for(int k=0;k<poly.size();k++){
				Segment edge=Segment(poly[k],poly[(k+1)%poly.size()]);
				Real dis1=mDis(edge,a);
				Real dis2=mDis(edge,b);
				if(sgn(dis1-R)<0||sgn(dis2-R)<0) fprintf(stderr,"b\n");
				if(isPara(edge,Segment(a,b))==false) continue;
				if(eq(dis1,R)&&eq(dis2,R)){
					Point p=edge.first;
					int s=sgn(crP(b-a,p-a));
					int id=s==-1?0:1;
					flg[id]=false;
				}
			}
			if(flg[0]==false&&flg[1]==false) continue;
			res+=abs(b-a);
//			fprintf(fp,"ctx.moveTo(%f,%f);\n",a.real()*10+600,a.imag()*10+600);
//			fprintf(fp,"ctx.lineTo(%f,%f);\n",b.real()*10+600,b.imag()*10+600);
//			fprintf(fp,"ctx.stroke();\n");
//			fprintf(fp,"%f %f %f %f\n",a.real(),a.imag(),b.real(),b.imag());
			vec.push_back(Segment(a,b));
		}
	}
	return res;
}

void init(){
	segs.clear();
	segs2.clear();
	poly.clear();
}

void input(){
	int N;
	scanf("%d%lf",&N,&R);
	if(N==0) exit(0);
	for(int i=0;i<N;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		Point p=Point(x,y);
		poly.push_back(p);
	}
}

int main(){
	for(int i=0;i<4;i++) dir[i]=Vector(dx[i],dy[i]);
	while(true){
		init();
		input();
/*			fprintf(fp,"<html>\n<head>\n<script type=\"text/javascript\">\n");
			fprintf(fp,"function draw(){\n");
			fprintf(fp,"var c=document.getElementById(\"canvas\");\n");
			fprintf(fp,"var ctx=c.getContext(\"2d\");\n");
			fprintf(fp,"ctx.beginPath();\n");*/
			Real ans=solve();
	/*		for(int i=0;i<poly.size();i++){
				fprintf(fp,"ctx.moveTo(%f,%f);\n",poly[i].real()*10+600,poly[i].imag()*10+600);
				fprintf(fp,"ctx.lineTo(%f,%f);\n",poly[(i+1)%poly.size()].real()*10+600,
					poly[(i+1)%poly.size()].imag()*10+600);
				fprintf(fp,"ctx.stroke();\n");
			}*/
	/*		fprintf(fp,"}\n");
			fprintf(fp,"</script></head>\n");
			fprintf(fp,"<body onload=\"draw()\">\n");
			fprintf(fp,"<canvas id=\"canvas\" width=\"2000\" height=\"2000\"></canvas>\n");
			fprintf(fp,"</body></html>\n");*/
		//	fclose(fp);

	//	Real ans=solve();
		printf("%.10f\n",ans);
//		bool flg=mergeIfAble(vec[23],vec[25]);
//		if(flg) fprintf(stderr,"true\n");
//		else fprintf(stderr,"false\n");
	}
	return 0;
}