Problem: The hobbits Frodo and Sam are carrying the One Ring to Mordor. In order not to be spotted by orcs, they decided to go through the mountains.

The mountain relief can be represented as a polyline with n points (x_i, y_i), numbered from 1 to n (x_i < x_{i + 1} for 1 ≤ i ≤ n - 1). Hobbits start their journey at the point (x_1, y_1) and should reach the point (x_n, y_n) to complete their mission.

The problem is that there is a tower with the Eye of Sauron, which watches them. The tower is located at the point (x_n, y_n) and has the height H, so the Eye is located at the point (x_n, y_n + H). In order to complete the mission successfully, the hobbits have to wear cloaks all the time when the Sauron Eye can see them, i. e. when there is a direct line from the Eye to the hobbits which is not intersected by the relief.

The hobbits are low, so their height can be considered negligibly small, but still positive, so when a direct line from the Sauron Eye to the hobbits only touches the relief, the Eye can see them.

<image> The Sauron Eye can't see hobbits when they are in the left position, but can see them when they are in the right position.

The hobbits do not like to wear cloaks, so they wear them only when they can be spotted by the Eye. Your task is to calculate the total distance the hobbits have to walk while wearing cloaks.

Input

The first line of the input contains two integers n and H (2 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ H ≤ 10^4) — the number of vertices in polyline and the tower height.

The next n lines contain two integers x_i, y_i each (0 ≤ x_i ≤ 4 ⋅ 10^5; 0 ≤ y_i ≤ 10^4) — the coordinates of the polyline vertices. It is guaranteed that x_i < x_{i + 1} for 1 ≤ i ≤ n - 1.

Output

Print one real number — the total distance the hobbits have to walk while wearing cloaks. Your answer will be considered correct if its absolute or relative error does not exceed 10^{-6} — formally, if your answer is a, and the jury's answer is b, your answer will be accepted if (|a - b|)/(max(1, b)) ≤ 10^{-6}.

Examples

Input


6 10
10 40
20 10
25 30
30 15
50 15
65 30


Output


70.4034587602


Input


9 5
0 0
5 10
15 10
20 0
25 11
30 0
35 10
50 10
60 5


Output


27.2787986124


Input


2 10000
0 10000
400000 0


Output


400124.9804748512

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

/***************************************************************
 * C++ routines for Computational Geometry (2D)
 * @nodim, @imAnik, @rebornplusplus
 ***************************************************************/

typedef double Tf;
typedef Tf Ti;	// use long long for exactness

const Tf PI = acos(-1);	// 4 * atan(1)
const Tf EPS = 1e-7;
const Tf INF = 1e10;

// returns 0 for (-EPS, EPS), -1 for <= -EPS and 1 for >= EPS
inline int dcmp(Tf x) {
	if(fabs(x) < EPS)
		return 0;
	else
		return x < 0 ? -1 : 1;
}

// returns an angle equivalent to th in [-PI, PI] range
inline Tf fix_acute(Tf th) {
	return th < -PI ? (th + 2 * PI) : th > PI ? (th - 2 * PI) : th;
}

struct Point {
	Ti x, y;
	Point(Ti x = 0, Ti y = 0) : x(x), y(y) {}

	bool operator == (const Point& u) const { return dcmp(x - u.x) == 0 and dcmp(y - u.y) == 0; }
	bool operator != (const Point& u) const { return !(*this == u); }
	bool operator < (const Point& u) const { return dcmp(x - u.x) < 0 or (dcmp(x - u.x) == 0 and dcmp(y - u.y) < 0); }
	bool operator > (const Point& u) const { return u < *this; }
	bool operator <= (const Point& u) const { return *this < u or *this == u; }
	bool operator >= (const Point& u) const { return *this > u or *this == u; }
	Point operator + (const Point& u) const { return Point(x + u.x, y + u.y); }
	Point operator - (const Point& u) const { return Point(x - u.x, y - u.y); }
//	Point operator * (const long long u) const { return Point(x * u, y * u); }
	Point operator * (const Tf u) const { return Point(x * u, y * u); }
	Point operator / (const Tf u) const { return Point(x / u, y / u); }

	// cross product of vectors *this and u
	Ti operator * (const Point& u) const { return x * u.y - y * u.x; }

	friend istream &operator >> (istream &is, Point &p) { return is >> p.x >> p.y; }
	friend ostream &operator << (ostream &os, const Point &p) { return os << p.x << " " << p.y; }
};

struct Segment {
	Point a, b;
	Segment() {}
	Segment(Point aa, Point bb) : a(aa), b(bb) {}
};

typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;

struct DirLine {
	Point p;
	Vector v;
	Tf ang;
	DirLine() {}
	DirLine(Point p, Vector v) : p(p), v(v) { ang = atan2(v.y, v.x); }
	bool operator<(const DirLine& u) const { return ang < u.ang; }
};

struct Star {
	int n;	// number of side of the star
	Tf r;	// radius of the circum-circle
	Star(int n, Tf r) : n(n), r(r) { }

	Tf area() {
		Tf theta = PI / n;
		Tf s = 2 * r * sin(theta);
		Tf R = 0.5 * s / tan(theta);
		Tf a = 0.5 * n * s * R;
		Tf a2 = 0.25 * s * s / tan(1.5 * theta);
		return a - n * a2;
	}
};

namespace Punctual {
	// distance between point a and b
	Tf distance(Point a, Point b) {
		Ti x = a.x - b.x, y = a.y - b.y;
		return sqrt(x * x + y * y);
	}
};  // namespace Punctual

namespace Vectorial {
	// dot product of vector a, b
	Ti dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }

	// cross product of vector a, b
	Ti cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }

	// actual length of vector a
	Tf length(Vector a) { return sqrt(dot(a, a)); }

	// squared length of vector a
	Ti sqLength(Vector a) { return dot(a, a); }

	// angle of vector u relative to +x axis
	Tf angle(Vector u) { return atan2(u.y, u.x); }

	// angle between vector a and b, signed
	Tf angleBetween(Vector a, Vector b) { return angle(b) - angle(a); }

	// rotate vector a counter clockwise with rad radians
	Vector rotate(Vector a, Tf rad) {
		assert(typeid(Ti) == typeid(Tf));
		return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad));
	}

	// rotate vector a counter clockwise by 90 degree
	Vector rotate90(Vector a) { return Vector(-a.y, a.x); }

	// rotate vector a counter clockwise with cos(th) = co and sin(th) = si
	Vector ccw(Vector a, Tf co, Tf si) {
		assert(typeid(Ti) == typeid(Tf));
		return Vector(a.x * co - a.y * si, a.y * co + a.x * si);
	}

	// rotate vector a clockwise with cos(th) = co and sin(th) = si
	Vector cw(Vector a, Tf co, Tf si) {
		assert(typeid(Ti) == typeid(Tf));
		return Vector(a.x * co + a.y * si, a.y * co - a.x * si);
	}

	// scales vector a by s such that length of a becomes s
	Vector scale(Vector a, Tf s) {
		assert(typeid(Ti) == typeid(Tf));
		return a / length(a) * s;
	}

	// returns an unit vector perpendicular to vector a
	Vector normal(Vector a) {
		assert(typeid(Ti) == typeid(Tf));
		Tf l = length(a);
		return Vector(-a.y / l, a.x / l);
	}
};  // namespace Vectorial

namespace ComplexVector {
	typedef complex<Tf> Point;
	typedef Point Vector;

	// dot product of vector a, b
	Tf dot(Vector a, Vector b) { return real(conj(a) * b); }

	// cross product of vector a, b
	Tf cross(Vector a, Vector b) { return imag(conj(a) * b); }

	// rotate vector a by rad radians
	Vector rotate(Vector a, Tf rad) { return a * exp(Point(0, rad)); }
};  // namespace ComplexVector

namespace Linear {
	using namespace Vectorial;

	// returns 1 if c is left of ab, 0 if on ab and -1 if right of ab
	int orient(Point a, Point b, Point c) {
		return dcmp(cross(b - a, c - a));
	}

	// returns true if point p is on segment s
	bool onSegment(Point p, Segment s) {
		return dcmp(cross(s.a - p, s.b - p)) == 0 and dcmp(dot(s.a - p, s.b - p)) <= 0;
	}
	// returns true if point p is on segment s
	bool onSegmentExclusive(Point p, Segment s) {
        if (p == s.a || p == s.b) return false;
        return onSegment(p, s);
	}

	// returns true if segment p and q touch or intersect
	bool segmentsIntersect(Segment p, Segment q) {
		if(onSegment(p.a, q)) return true;
		if(onSegment(p.b, q)) return true;
		if(onSegment(q.a, p)) return true;
		if(onSegment(q.b, p)) return true;  //Case of touch

		Ti c1 = cross(p.b - p.a, q.a - p.a);
		Ti c2 = cross(p.b - p.a, q.b - p.a);
		Ti c3 = cross(q.b - q.a, p.a - q.a);
		Ti c4 = cross(q.b - q.a, p.b - q.a);
		return dcmp(c1) * dcmp(c2) < 0 and dcmp(c3) * dcmp(c4) < 0;
	}

	bool linesParallel(Line p, Line q) {
		return dcmp(cross(p.b - p.a, q.b - q.a)) == 0;
	}

	bool linesCollinear(Line p, Line q) {
		return !orient(p.a, p.b, q.a) and !orient(p.a, p.b, q.b);
	}

	// lines are represented as a ray from a point: (point, vector)
	// returns false if two lines (p, v) and (q, w) are parallel or collinear
	// true otherwise, intersection point is stored at o via reference
	bool lineLineIntersection(Point p, Vector v, Point q, Vector w, Point& o) {
		assert(typeid(Ti) == typeid(Tf));
		if(dcmp(cross(v, w)) == 0) return false;
		Vector u = p - q;
		Tf k = (Tf) cross(w, u) / cross(v, w);
		o = p + v * k;
		return true;
	}

	// returns false if two lines p and q are parallel or collinear
	// true otherwise, intersection point is stored at o via reference
	bool lineLineIntersection(Line p, Line q, Point& o) {
		return lineLineIntersection(p.a, p.b - p.a, q.a, q.b - q.a, o);
	}

};  // namespace Linear

const int MAXN = 5e5+7;
Point pts[MAXN];

bool canSee(Point eye, Point obstacle, Point query) {
    return Linear::orient(obstacle, eye, query) >= 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, H;
    cin >> n >> H;

    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        pts[i].x = x;
        pts[i].y = y;
    }

    Point eye(pts[n].x, pts[n].y+H);
    Point obstacle(pts[n]);

    double ans = 0;
    for (int i = n-1; i > 0; i--) {
        if (!canSee(eye, obstacle, pts[i])) continue;

        if ((eye.y-obstacle.y)*(pts[i+1].x-pts[i].x) == (pts[i+1].y-pts[i].y)*(eye.x-obstacle.x)) {
            ans += Punctual::distance(pts[i], pts[i+1]);
        } else {
            Point dan;
            Linear::lineLineIntersection(Segment(eye, obstacle), Segment(pts[i], pts[i+1]), dan);
            if (pts[i+1].x < dan.x) dan = pts[i+1];
            ans += Punctual::distance(pts[i], dan);
        }

        obstacle = pts[i];
    }

    cout << fixed << setprecision(10) << ans << "\n";

    return 0;
}