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

Difficulty: VERY_HARD
Tags: Geometry

Sorting
Skill types: Sorting

Starter code:

Solutions:
import sys
input = sys.stdin.readline
(n, H) = map(int, input().split())
points = [tuple(map(int, input().split())) for _ in range(n)]
eye = (points[-1][0], points[-1][1] + H)
peak = points[-1]
out = 0

def dot(a, b):
	return a[0] * b[0] + a[1] * b[1]

def sub(a, b):
	return (a[0] - b[0], a[1] - b[1])

def norm(a):
	return (a[0] ** 2 + a[1] ** 2) ** 0.5
for _ in range(n - 2, -1, -1):
	p1 = points[_]
	p2 = points[_ + 1]
	vecP = sub(peak, eye)
	vecR = (vecP[1], -vecP[0])
	vecP1 = sub(p1, eye)
	vecP2 = sub(p2, eye)
	h1 = dot(vecP1, vecR)
	h2 = dot(vecP2, vecR)
	if h2 >= 0:
		if h1 >= 0:
			out += norm(sub(p1, p2))
			peak = p1
	elif h1 >= 0:
		out += norm(sub(p1, p2)) * (h1 / (h1 - h2))
		peak = p1
print(out)


from collections import deque
from math import floor, atan2, sqrt, ceil, pi, cos, sin
import sys

class Point:

	def __init__(self, x=0, y=0):
		self.x = x
		self.y = y

	def __lt__(self, p):
		return (self.x, self.y) < (p.x, p.y)

	def __eq__(self, p):
		return (self.x, self.y) == (p.x, p.y)

	def __gt__(self, p):
		return (self.x, self.y) > (p.x, p.y)

	def __add__(self, p):
		return Point(self.x + p.x, self.y + p.y)

	def __sub__(self, p):
		return Point(self.x - p.x, self.y - p.y)

	def __mul__(self, d):
		return Point(self.x * d, self.y * d)

	def __truediv__(self, d):
		return Point(self.x / d, self.y / d)

	def __hash__(self):
		return hash((self.x, self.y))

	def __str__(self):
		return '(' + str(self.x) + ',' + str(self.y) + ')'

	def __repr__(self):
		return self.__str__()

	def dot(self, p):
		return self.x * p.x + self.y * p.y

	def self_cross(self, p):
		return self.x * p.y - self.y * p.x

	def cross(self, a, b):
		return (a - self).self_cross(b - self)

	def dist2(self):
		return self.x * self.x + self.y * self.y

	def dist(self):
		return math.sqrt(self.dist2())

	def angle(self):
		return math.atan2(self.y, self.x)

	def unit(self):
		return self / self.dist()

	def perp(self):
		return Point(-1 * self.y, self.x)

	def normal(self):
		return self.perp() / self.unit()

	def rotate(a):
		return P(self.x * math.cos(a) - self.y * math.sin(a), self.x + math.sin(a) + self.y * math.cos(a))
splitted = [int(amit) for amit in sys.stdin.readline().split(' ')]
n = splitted[0]
H = splitted[1]
points = list()
for i in range(n):
	points.append([int(amit) for amit in sys.stdin.readline().split(' ')])
eyeLoc = points[len(points) - 1].copy()
eyeLoc[1] += H

def adjustAngle(theta):
	while not 0 <= theta < 2 * pi:
		if theta < 0:
			theta += 2 * pi
		else:
			theta -= 2 * pi
	return theta

def dist(p1, p2):
	return sqrt((p2[1] - p1[1]) ** 2 + (p2[0] - p1[0]) ** 2)

def dist2(p1, p2):
	return (p2[1] - p1[1]) ** 2 + (p2[0] - p1[0]) ** 2

def binsearch(minAngle, eyeLoc, endpoint1, endpoint2):
	low = endpoint1
	high = endpoint2
	while dist2(low, high) > 1e-12:
		mid = [0.5 * low[0] + 0.5 * high[0], 0.5 * low[1] + 0.5 * high[1]]
		if adjustAngle(atan2(mid[1] - eyeLoc[1], mid[0] - eyeLoc[0])) <= minAngle:
			low = mid
		else:
			high = mid
	return low

def rayLineSegIntersection(rayPoint, rayDir, p1, p2):
	x = rayPoint[0]
	y = rayPoint[1]
	x1 = p1[0]
	x2 = p2[0]
	y1 = p1[1]
	y2 = p2[1]
	r = None
	s = None
	d = None
	dx = rayDir[0]
	dy = rayDir[1]
	if dy / dx != (y2 - y1) / (x2 - x1):
		d = dx * (y2 - y1) - dy * (x2 - x1)
		if d != 0:
			r = ((y - y1) * (x2 - x1) - (x - x1) * (y2 - y1)) / d
			s = ((y - y1) * dx - (x - x1) * dy) / d
			if r >= 0 and s >= 0 and (s <= 1):
				return [x + r * dx, y + r * dy]
	return p1
minAngle = adjustAngle(atan2(points[len(points) - 1][1] - eyeLoc[1], points[len(points) - 1][0] - eyeLoc[0]))
pointIndex = len(points) - 1
totalDistWithHoodie = 0
while pointIndex >= 1:
	endpoint1 = points[pointIndex - 1]
	endpoint2 = points[pointIndex]
	if adjustAngle(atan2(endpoint2[1] - eyeLoc[1], endpoint2[0] - eyeLoc[0])) == minAngle:
		if adjustAngle(atan2(endpoint1[1] - eyeLoc[1], endpoint1[0] - eyeLoc[0])) <= minAngle:
			totalDistWithHoodie += dist(endpoint1, endpoint2)
	else:
		pointInView = rayLineSegIntersection(eyeLoc, [cos(minAngle), sin(minAngle)], endpoint1, endpoint2)
		totalDistWithHoodie += dist(endpoint1, pointInView)
	curAngle = adjustAngle(atan2(endpoint1[1] - eyeLoc[1], endpoint1[0] - eyeLoc[0]))
	if curAngle < minAngle:
		minAngle = curAngle
	pointIndex -= 1
sys.stdout.write('%s' % totalDistWithHoodie)


import math
import sys

def ccw(x1, y1, x2, y2, x3, y3):
	return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) > 0
(n, H) = [int(i) for i in input().split()]
x = [None] * n
y = [None] * n
for i in range(n):
	(x[i], y[i]) = [int(i) for i in sys.stdin.readline().strip().split()]
(Xe, Ye) = (x[-1], y[-1] + H)
(Xp, Yp) = (x[-1], y[-1])
ans = 0
for i in range(n - 2, -1, -1):
	if ccw(Xe, Ye, Xp, Yp, x[i], y[i]):
		continue
	m1 = (y[i + 1] - y[i]) / (x[i + 1] - x[i])
	m2 = (Ye - Yp) / (Xe - Xp) if Xe != Xp else math.inf
	if (x[i + 1] - x[i]) * (Ye - Yp) == (y[i + 1] - y[i]) * (Xe - Xp):
		ans += math.sqrt((x[i + 1] - x[i]) ** 2 + (y[i + 1] - y[i]) ** 2)
	else:
		x_int = (Ye - y[i] + m1 * x[i] - m2 * Xe) / (m1 - m2) if m2 != math.inf else Xe
		ans += (x_int - x[i]) * math.sqrt(1 + m1 ** 2)
	(Xp, Yp) = (x[i], y[i])
print(ans)