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;

#define st first
#define nd second
#define pb push_back
#define cl(x,v) memset((x), (v), sizeof(x))
#define db(x) cerr << #x << " == " << x << endl
#define dbs(x) cerr << x << endl
#define _ << ", " <<

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<int, pii> piii;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> plll;
typedef vector<int> vi;
typedef vector <vi> vii;

const ld EPS = 1e-9, PI = acos(-1.);
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f, MOD = 1e9+7;
const int N = 2e5+5;

typedef double type;

bool ge(type x, type y) { return x + EPS > y; }
bool le(type x, type y) { return x - EPS < y; }
bool eq(type x, type y) { return ge(x, y) and le(x, y); }

struct point {
    type x, y;

    point() : x(0), y(0) {}
    point(type x, type y) : x(x), y(y) {}

    point operator -() { return point(-x, -y); }
    point operator +(point p) { return point(x+p.x, y+p.y); }
    point operator -(point p) { return point(x-p.x, y-p.y); }

    point operator *(type k) { return point(k*x, k*y); }
    point operator /(type k) { return point(x/k, y/k); }

    type operator *(point p) { return x*p.x + y*p.y; }
    type operator %(point p) { return x*p.y - y*p.x; }

    bool operator ==(point p) { return x == p.x and y == p.y; }
    bool operator !=(point p) { return x != p.x  or y != p.y; }
    bool operator <(const point p) const { return (x < p.x) or (x == p.x and y < p.y); }

    // o is the origin, p is another point
    // dir == +1 => p is clockwise from this
    // dir ==  0 => p is colinear with this
    // dir == -1 => p is counterclockwise from this
    int dir(point o, point p) {
        type x = (*this - o) % (p - o);
        return ge(x,0) - le(x,0);
    }

    bool on_seg(point p, point q) {
        if (this->dir(p, q)) return 0;
        return ge(x, min(p.x, q.x)) and le(x, max(p.x, q.x)) and
            ge(y, min(p.y, q.y)) and le(y, max(p.y, q.y));
    }

    ld abs() { return sqrt(x*x + y*y); }
    type abs2() { return x*x + y*y; }
    ld dist(point q) { return (*this - q).abs(); }
    type dist2(point q) { return (*this - q).abs2(); }

    ld arg() { return atan2l(y, x); }

    /*// Project point on vector y
    point project(point q) { return q * ((*this * q) / (q * q)); }

    // Project point on line generated by points x and y
    point project(point p, point q) { return p + (*this - p).project(q-p); }

    ld dist_line(point p, point q) { return dist(project(p, q)); }

    ld dist_seg(point p, point q) {
        return project(p, q).on_seg(p, q) ? dist_line(p, q) :  min(dist(p), dist(q)));
    }*/

    point rotate(ld sin, ld cos) { return point(cos*x-sin*y, sin*x+cos*y); }
    point rotate(ld a) { return rotate(sin(a), cos(a)); }
    // rotate around the argument of vector p
    point rotate(point p) { return rotate(p.x / p.abs(), p.y / p.abs()); }
};

ostream &operator<<(ostream &os, const point &p) {
  os << "(" << p.x << "," << p.y << ")"; 
  return os;
}

int direction(point o, point p, point q) { return p.dir(o, q); }

point lines_intersect(point p, point q, point a, point b) {
    point r = q-p, s = b-a, c(p%q, a%b);
    if (eq(r%s,0)) return point(INF, INF);
    return point(point(r.x, s.x) % c, point(r.y, s.y) % c) / (r%s);
}

point p[N];

int main(){
    int n,h;
    scanf("%d %d",&n,&h);
    priority_queue <pair<pair<int,ld>,int>> pq;
    for(int i=0;i<n;i++){
        scanf("%lf %lf",&p[i].x, &p[i].y);
    }
    point eye = point(p[n-1].x,p[n-1].y+h);
    point eixo = point(1,0);
    for(int i=0;i<n;i++){
        //create priority queue with the greatest "barrier" in the moment
        point v = (eye-p[i]);
        //normalize vector
        v = v/v.abs();
        //calculating cos
        ld angle = v*eixo;
        int dir = 0;
        //if v.y is negative, means the point is above the eye
        //dir = 1 above, dir = 1 below
        //above comes first in order
        //to sort between above ones, use negative cos  
        if(v.y < -EPS) dir = 1, angle = -angle;
        pq.push({{dir,angle},-i});
    }
    ld ans = 0;
    for(int i=0;i<n-1;i++){
        bool walk = false;
        //empty queue until reaches a barrier greater than i
        while(pq.top().nd >= -i){
            //if while emptying the queue the point is not removed, it means the next barrier blocks all vision  
            if(pq.top().nd == -i) walk = true;
            //if is removed barrier only blocks partial (maybe nothing)
            pq.pop();
        }
        if(walk){
            int nxt = -pq.top().nd;
            point stop = lines_intersect(p[i],p[i+1],eye,p[nxt]);
            //corner case, collinear
            if(stop.x == INF and stop.y == INF) stop = p[i+1];
            ans += (stop-p[i]).abs();
        }
    }
    printf("%.10lf\n",ans);
    return 0;
}