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 <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

//#define ENVIRONMENT_LINKED_ACL

#ifdef ENVIRONMENT_LINKED_ACL
#include <atcoder/convolution>
#include <atcoder/lazysegtree>
#include <atcoder/segtree.hpp>
#endif

//#define ENVIRONMENT_LINKED_BOOST

#ifdef ENVIRONMENT_LINKED_BOOST
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#endif

using namespace std;
using uint = unsigned int;
using ll   = long long;
using ull  = unsigned long long;
#define REP(i, a, b)    for (ll i = a; i < b; ++i)
#define REPREV(i, a, b) for (ll i = a; i > b; --i)

const int _ = []() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    return 0;
}();

template <typename value_t>
void resize(value_t& v, const value_t& val) { v = val; }
template <typename vec_t, typename value_t, typename... arg_t>
void resize(std::vector<vec_t>& v, const value_t& val, int size, arg_t... arg) {
    v.resize(size);
    for (auto& c : v) resize(c, val, arg...);
}

template <typename A, typename B>
void chmin(A& a, const B& b) {
    a = min(a, static_cast<A>(b));
};
template <typename A, typename B>
void chmax(A& a, const B& b) {
    a = max(a, static_cast<A>(b));
};

#include <algorithm>
#include <random>
#include <vector>

const double GEOMETRY_EPS = 1e-8;
const double GEOMETRY_INF = 1e12;
const double GEOMETRY_PI  = 3.14159265358979323846264338327950288;

struct comp {
    double x;
    double y;
};

double norm(comp a) { return sqrt(a.x * a.x + a.y * a.y); }
double normsquare(comp a) { return a.x * a.x + a.y * a.y; }
double abs(comp a) { return norm(a); }
double dot(comp a, comp b) { return a.x * b.x + a.y * b.y; }
double cross(comp a, comp b) { return a.x * b.y - a.y * b.x; }

comp conjugate(comp a) { return {a.x, -a.y}; }
comp operator~(comp a) { return conjugate(a); }

comp operator+(comp a, comp b) { return {a.x + b.x, a.y + b.y}; }
comp operator-(comp a, comp b) { return {a.x - b.x, a.y - b.y}; }
comp operator*(comp a, comp b) { return {a.x * b.x - a.y * b.y, a.y * b.x + a.x * b.y}; }
comp operator*(comp a, double b) { return a * comp{b, 0}; }
comp operator*(double a, comp b) { return comp{a, 0} * b; }
comp operator/(comp a, comp b) { return a * ~b * (1.0 / normsquare(b)); }
comp operator/(comp a, double b) { return (1.0 / b) * a; }
bool operator==(comp a, comp b) { return abs(a.x - b.x) < GEOMETRY_EPS && abs(a.y - b.y) < GEOMETRY_EPS; }
bool operator!=(comp a, comp b) { return !(a == b); }

comp rotate90(comp a) { return {-a.y, a.x}; }
comp rotateminus90(comp a) { return {a.y, -a.x}; }

//aとbの距離
double dist(comp a, comp b) {
    return norm(a - b);
}

//直線s + td   s:始点、d:向きの単位ベクトル
struct line {
    comp s;
    comp d;
    double t_min;
    double t_max;

    comp startpoint() { return s + d * t_min; }
    comp endpoint() { return s + d * t_max; }
};

//円 中心c 半径r
struct circle {
    comp c;
    double r;
};

//直線のパラメータ、始点s,終点g,フラグがTなら線分
line getline(comp s, comp g, bool segment) {
    if (abs(g - s) < GEOMETRY_EPS) return {s, {0, 0}, -GEOMETRY_INF, GEOMETRY_INF};
    return {s, (g - s) / abs(g - s), segment ? 0 : -GEOMETRY_INF, segment ? abs(g - s) : GEOMETRY_INF};
}

//垂直二等分線
line perpendicular_bisector(comp a, comp b) {
    if (a == b) return line{a, {0, 0}, 0, 0};
    comp c = (a + b) / 2.0;
    return getline(c, c + rotate90(b - a), false);
}

//線分の延長直線
line extensionline(line l) {
    return {l.s, l.d, -GEOMETRY_INF, GEOMETRY_INF};
}

//平行か判定
bool parallel(line a, line b) {
    return abs(dot(a.d, rotate90(b.d))) < GEOMETRY_EPS;
}

//線分a,bは交差するか、するときは交点も返す
std::pair<bool, comp> getcrosspoint(line l1, line l2) {
    comp a = l1.s;
    comp b = l1.d;
    comp c = l2.s;
    comp d = l2.d;
    comp e = c - a;
    if (abs(cross(b, d)) < GEOMETRY_EPS) return {false, {0, 0}};
    double t = cross(e, d) / cross(b, d);
    double s = cross(e, b) / cross(b, d);
    if (t + GEOMETRY_EPS < l1.t_min || l1.t_max + GEOMETRY_EPS < t) return {false, {0, 0}};
    if (s + GEOMETRY_EPS < l2.t_min || l2.t_max + GEOMETRY_EPS < s) return {false, {0, 0}};
    return {true, t * b + a};
}

//点と線分の距離。線分であることに注意
double dist(line l, comp p) {
    line normal = line{p, rotate90(l.d), -GEOMETRY_INF, GEOMETRY_INF};
    auto ret    = getcrosspoint(l, normal);
    if (ret.first)
        return dist(ret.second, p);
    else
        return fmin(dist(p, l.startpoint()), dist(p, l.endpoint()));
}

//pは線分l上の点か、フラグがTなら、端点も許す
bool point_on_line(line l, comp p, bool edge_ok = true) {
    if (dist(l, p) > GEOMETRY_EPS) return false;
    if (!edge_ok) {
        if (p == l.startpoint()) return false;
        if (p == l.endpoint()) return false;
    }
    return true;
}

//凸包。x座標最小の中でy座標最小の点から反時計回りにインデックスを格納。フラグがTなら、凸包の辺上の点も格納。もし同一点があるなら、インデックスが最初のものが格納されるO(nlogn)
void convex_hull(const std::vector<comp>& vertices, std::vector<int>& ans, bool points_on_line) {
    ans.clear();
    if (vertices.empty()) return;

    std::vector<int> v(vertices.size());
    for (int i = 0; i < vertices.size(); ++i) v[i] = i;

    sort(v.begin(), v.end(), [&](int a, int b) {
        if (abs(vertices[a].x - vertices[b].x) < GEOMETRY_EPS) return vertices[a].y > vertices[b].y + GEOMETRY_EPS;
        return vertices[a].x + GEOMETRY_EPS < vertices[b].x;
    });

    std::vector<std::vector<int>> s;
    for (int i = 0; i < v.size(); ++i) {
        if (i > 0 && vertices[v[i]] == vertices[v[i - 1]]) continue;
        if (s.empty() || abs(vertices[s.back()[0]].x - vertices[v[i]].x) > GEOMETRY_EPS) s.push_back({});
        s.back().push_back(v[i]);
    }

    if (s.size() == 1) {
        if (points_on_line) {
            ans = s[0];
            reverse(ans.begin(), ans.end());
        }
        else {
            if (s[0].size() == 1)
                ans.push_back(s[0][0]);
            else
                ans.push_back(s[0].back()), ans.push_back(s[0][0]);
        }
        return;
    }

    std::vector<int> upper, lower;
    lower.push_back(s[0].back());
    for (int i = 1; i < s.size(); ++i) {
        while (lower.size() > 1) {
            comp a = vertices[s[i].back()] - vertices[lower[lower.size() - 2]];
            comp b = vertices[lower.back()] - vertices[lower[lower.size() - 2]];
            if (points_on_line && cross(a, b) > GEOMETRY_EPS) {
                lower.pop_back();
                continue;
            }
            else if (!points_on_line && cross(a, b) + GEOMETRY_EPS > 0.0) {
                lower.pop_back();
                continue;
            }
            break;
        }
        lower.push_back(s[i].back());
    }

    int cur = 1;
    for (int i = 1; i < s.size() - 1; ++i) {
        if (s[i].back() == lower[cur]) {
            s[i].pop_back();
            ++cur;
        }
    }

    upper.push_back(s[0][0]);
    for (int i = 1; i < s.size(); ++i) {
        if (s[i].empty()) continue;
        while (upper.size() > 1) {
            comp a = vertices[s[i][0]] - vertices[upper[upper.size() - 2]];
            comp b = vertices[upper.back()] - vertices[upper[upper.size() - 2]];
            if (points_on_line && cross(b, a) > GEOMETRY_EPS) {
                upper.pop_back();
                continue;
            }
            else if (!points_on_line && cross(b, a) + GEOMETRY_EPS > 0.0) {
                upper.pop_back();
                continue;
            }
            break;
        }
        upper.push_back(s[i][0]);
    }

    ans.push_back(s[0].back());

    for (int i = 1; i < lower.size() - 1; ++i) ans.push_back(lower[i]);

    if (points_on_line) {
        for (auto it = s.back().rbegin(); it != s.back().rend(); ++it) {
            ans.push_back(*it);
        }
    }
    else {
        if (s.back().size() == 1) {
            ans.push_back(s.back()[0]);
        }
        else {
            ans.push_back(s.back().back());
            ans.push_back(s.back()[0]);
        }
    }

    for (int i = upper.size() - 2; i >= 1; --i) ans.push_back(upper[i]);

    if (s[0].size() > 1) {
        if (points_on_line) {
            for (int i = 0; i < s[0].size() - 1; ++i) ans.push_back(s[0][i]);
        }
        else
            ans.push_back(s[0][0]);
    }
}

//最遠点対を求める。O(nlogn)もし頂点集合が1点の時は同じ頂点のペアが返される
std::pair<comp, comp> calipers(const std::vector<comp>& vertices) {
    std::vector<int> convex_hull_index;
    convex_hull(vertices, convex_hull_index, false);

    if (convex_hull_index.size() <= 1) return {vertices[0], vertices[0]};
    if (convex_hull_index.size() == 2) return {vertices[convex_hull_index[0]], vertices[convex_hull_index[1]]};

    std::vector<comp> v;
    for (int i : convex_hull_index) v.push_back(vertices[i]);

    auto cmp_x = [](comp a, comp b) {
        if (abs(a.x - b.x) < GEOMETRY_EPS) return a.y + GEOMETRY_EPS < b.y;
        return a.x + GEOMETRY_EPS < b.x;
    };

    int si = 0, sj = 0;
    for (int k = 0; k < v.size(); ++k) {
        if (cmp_x(v[k], v[si])) si = k;
        if (cmp_x(v[sj], v[k])) sj = k;
    }

    int ansi = 0, ansj = 0;
    double d = 0;

    int i = si;
    int j = sj;
    while (i != sj || j != si) {
        if (d + GEOMETRY_EPS < dist(v[i], v[j])) {
            ansi = i;
            ansj = j;
            d    = dist(v[i], v[j]);
        }
        if (cross(v[(j + 1) % v.size()] - v[j], v[(i + 1) % v.size()] - v[i]) > GEOMETRY_EPS)
            i = (i + 1) % v.size();
        else
            j = (j + 1) % v.size();
    }

    return {v[ansi], v[ansj]};
}

//最小包含円。期待値O(n)
circle mini_disc(const std::vector<comp>& vertices, int seed = 0) {
    if (vertices.empty()) return {{0, 0}, 0};
    if (vertices.size() == 1) return {vertices[0], 0};

    std::vector<comp> v = vertices;
    std::mt19937 mt(seed);
    std::shuffle(v.begin(), v.end(), mt);

    auto in_disc = [](comp p, circle c) {
        return dist(p, c.c) + GEOMETRY_EPS < c.r;
    };
    auto make_disc = [](comp a, comp b) {
        return circle({(a + b) / 2.0, dist(a, b) / 2.0});
    };

    circle ans = make_disc(v[0], v[1]);
    for (int i = 2; i < v.size(); ++i) {
        if (in_disc(v[i], ans)) continue;

        ans = make_disc(v[0], v[i]);
        for (int j = 1; j < i; ++j) {
            if (in_disc(v[j], ans)) continue;

            ans = make_disc(v[j], v[i]);
            for (int k = 0; k < j; ++k) {
                if (in_disc(v[k], ans)) continue;

                comp c = getcrosspoint(perpendicular_bisector(v[i], v[j]), perpendicular_bisector(v[i], v[k])).second;
                ans    = {c, dist(c, v[i])};
            }
        }
    }
    return ans;
}

int main() {
    ll n;
    cin >> n;
    double H;
    cin >> H;
    vector<comp> P(n);
    REP(i, 0, n) {
        cin >> P[i].x >> P[i].y;
    }
    double ans = 0;
    int cur    = n - 2;
    comp pos   = P[n - 1];
    comp eye   = {P[n - 1].x, P[n - 1].y + H};
    while (true) {
        ans += dist(pos, P[cur]);
        pos = P[cur];

        if (cur == 0) break;

        comp p2e  = eye - pos;
        comp p2np = P[cur - 1] - pos;
        if (dot(rotate90(p2e), p2np) + GEOMETRY_EPS > 0) {
            --cur;
            continue;
        }
        bool cont = false;

        line e = getline(pos, eye, false);

        REPREV(i, cur - 2, -1) {
            line l   = getline(P[i], P[i + 1], true);
            auto ret = getcrosspoint(e, l);
            if (ret.first) {
                cur  = i;
                pos  = ret.second;
                cont = true;
                break;
            }
        }
        if (!cont) break;
    }
    cout << ans << endl;
    return 0;
}