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 <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cmath>
#include <functional>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <set>
#ifdef XLor
  #define dbg(args...) cout << "\033[32;1m" << #args << " -> ", err(args)
  void err() { std::cout << "\033[39;0m" << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
using ll = long long;
using PII = pair<int,int>;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 200000 + 5;

namespace Geometry {
  const double eps = 1e-6;
  const double pi = acos(-1.0);

  inline int sign(double x) {
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
  }
  inline int dcmp(double x, double y) {
    return sign(x - y);
  }
  inline int zero(double x) {
    return fabs(x) < eps;
  }

  // x 在 [l, r] 内或 [r, l] 内
  inline int inMid(double l, double r, double x) {
    return dcmp(l, x) * dcmp(r, x) <= 0;
  }

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

    void read() { scanf("%lf%lf", &x, &y); }

    Point operator + (const Point& b) const { return Point(x + b.x, y + b.y); }
    Point operator - (const Point& b) const { return Point(x - b.x, y - b.y); }
    Point operator * (double p) { return Point(x * p, y * p); }
    Point operator / (double p) { return Point(x / p, y / p); }

    bool operator == (const Point& b) const { return dcmp(x, b.x) == 0 && dcmp(y, b.y) == 0; }
    bool operator != (const Point& b) const { return !(*this == b); }
    bool operator < (const Point& b) const {
      int f = dcmp(x, b.x);
      if (f == -1) return 1;
      else if (f == 1) return 0;
      else return dcmp(y, b.y) == -1;
    }

    double abs() { return sqrt(x * x + y * y); }
    double abs2() { return x * x + y * y; }
    double distance(const Point& b) { return (*this - b).abs(); }

    // 逆时针旋转
    Point rot90(){ return Point(-y, x); }
    Point rot(double r) {
      return Point(x * cos(r) - y * sin(r), x * sin(r) + y * cos(r));
    }
    Point unit() { return *this / abs(); }
  };

  ostream& operator<<(ostream& out, const Point& u) {
    return out << "(" << u.x << ", " << u.y << ")";
  }
  istream& operator>>(istream& in, Point& u) {
    return in >> u.x >> u.y;
  }

  double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
  double angle(Point a, Point b) { return acos(dot(a, b) / a.abs() / b.abs()); }
  double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
  double cross(Point a, Point b, Point c) { return cross(b - a, c - a); }

  // C 在 B 的逆时针方向 1, 顺时针方向 -1, 共线 0
  int clockwise(Point a, Point b, Point c) { return sign(cross(b - a, c - a)); }

  // p[0] -> p[1]
  struct Line {
    Point p[2];
    Line() {}
    Line(Point a, Point b) { p[0] = a; p[1] = b; }

    void read() { p[0].read(); p[1].read(); }
    Point& operator [](int i) { return p[i]; }
    Point dir() { return p[1] - p[0]; }

    // q 在直线上的投影点
    Point projection(const Point& q) {
      Point k = p[1] - p[0];
      return p[0] + k * (dot(q - p[0], k) / k.abs2());
    }
    // q 在直线上的对称点
    Point reflection(const Point& q) {
      return projection(q) * 2 - q;
    }
  };

  // q 是否在线段 L 上
  bool onSegment(Line l, const Point& q) {
    return sign(cross(q - l[0], l[1] - l[0])) == 0 &&
      inMid(l[0].x, l[1].x, q.x) && inMid(l[0].y, l[1].y, q.y);
  }
  // q 是否在线段 AB 上
  bool onSegment(Point a, Point b, Point q) {
    return onSegment(Line(a, b), q);
  }
  // 直线 L1 和 L2 是否平行
  bool isParallel(Line l1, Line l2) {
    return sign(cross(l1.dir(), l2.dir())) == 0;
  }
  // 射线 L1 和 L2 的方向是否相同
  bool isSameDir(Line l1, Line l2) {
    return isParallel(l1, l2) && sign(dot(l1.dir(), l2.dir())) == 1;
  }
  // 直线 L1 和 L2 是否正交
  bool isOrthogonal(Line l1, Line l2) {
    return sign(dot(l1.dir(), l2.dir())) == 0;
  }

  // 区间 [l1, r1] 和 [l2, r2] 是否相交
  bool intersect(double l1, double r1, double l2, double r2) {
    if (l1 > r1) swap(l1, r1);
    if (l2 > r2) swap(l2, r2);
    return !(dcmp(r1, l2) == -1 || dcmp(r2 ,l1) == -1);
  }
  // 线段 P1P2 和 Q1Q2 是否相交
  bool isSegmentIntersect(Point p1, Point p2, Point q1, Point q2) {
    return intersect(p1.x, p2.x, q1.x, q2.x) &&
      intersect(p1.y, p2.y, q1.y, q2.y) &&
      sign(cross(p1, p2, q1)) * sign(cross(p1, p2, q2)) <= 0 &&
      sign(cross(q1, q2, p1)) * sign(cross(q1, q2, p2)) <= 0;
  }
  // 线段 L1 和 L2 是否相交
  bool isSegmentIntersect(Line l1, Line l2) {
    return isSegmentIntersect(l1[0], l1[1], l2[0], l2[1]);
  }

  // 获取直线 P1P2 和 Q1Q2 的交点
  Point getLineIntersection(Point p1, Point p2, Point q1, Point q2) {
    double a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
    return (p1 * a2 + p2 * a1) / (a1 + a2);
  }
  // 获取直线 L1 和 L2 的交点
  Point getLineIntersection(Line l1, Line l2) {
    return getLineIntersection(l1[0], l1[1], l2[0], l2[1]);
  }

  // 获取点 Q 到线段 L 的距离
  double disPointSegment(Point q, Line l) {
    Point k = l.projection(q);
    if (onSegment(l, k)) {
      return q.distance(k);
    } else {
      return min(q.distance(l[0]), q.distance(l[1]));
    }
  }
  // 获取线段 L1 和 L2 的距离
  double disSegment(Line l1, Line l2) {
    if (isSegmentIntersect(l1, l2)) return 0.0;
    return min(min(disPointSegment(l2[0], l1), disPointSegment(l2[1], l1)),
      min(disPointSegment(l1[0], l2), disPointSegment(l1[1], l2)));
  }
}
using namespace Geometry;

int n, H, xx[maxn], yy[maxn];

int main() {
  scanf("%d%d", &n, &H);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", xx + i, yy + i);
  }
  double ans = 0.0;
  Point sun(xx[n], yy[n] + H);
  Line lsun(sun, Point(xx[n], yy[n]));
  bool up = false;
  for (int i = n - 1; i >= 1; i--) {
    Point pre(xx[i], yy[i]);
    Point nxt(xx[i + 1], yy[i + 1]);
    Line cur(pre, nxt);
    if (isParallel(lsun, cur)) {
      int dir1 = clockwise(sun, nxt, lsun[1]);
      int dir2 = clockwise(sun, pre, lsun[1]);
      if (dir1 >= 0 && dir2 >= 0) {
        ans += pre.distance(nxt);
      }
      // if (!up) {
      //   ans += pre.distance(nxt);
      // } else {
      // }
    } else {
      Point its = getLineIntersection(lsun, cur);
      if (its != nxt && onSegment(cur, its)) {
        ans += its.distance(pre);
      } else {
        int dir1 = clockwise(sun, nxt, lsun[1]);
        int dir2 = clockwise(sun, pre, lsun[1]);
        if (dir1 >= 0 && dir2 >= 0) {
          // if (!up) {
          //   int dir = clockwise(sun, pre, nxt);
          //   assert(dir != 0);
          //   if (dir == 1) {
          //     ans += pre.distance(nxt);
          //   }
          // } else {
          //   ans += pre.distance(nxt);
          // }
          ans += pre.distance(nxt);
        }
      }
    }
    if (yy[i] > yy[n] + H) {
      up = true;
    }
    if (clockwise(sun, pre, lsun[1]) == 1) {
      lsun = Line(sun, pre);
    }
    dbg(ans, lsun[1].x, lsun[1].y);
  }
  printf("%.10lf\n", ans);
  return 0;
}