Illuminating the Valleys on a Mountain

You are given a mountain described by a polygon. The polygon is given by n points \((x_i,y_i)\) for \(i=1,2,\dots,n\) where \(n\) is an odd integer. In addition, the polygon is closed by two extra points \((x_1, -\infty)\) and \((x_n, -\infty)\). For every integer index \(i\) satisfying \(1 < i < n\) and \(i\ \bmod\ 2 = 1\), the point \((x_i,y_i)\) is a valley of the mountain.

You are also given a height \(h\). You can place point light sources at any horizontal location with fixed height \(h\). A valley \(V=(x_V,y_V)\) is considered illuminated by a light source placed at \(S=(x,h)\) if the line segment connecting \(S\) and \(V\) does not pass through the interior of the mountain; in other words, the entire segment lies on or above the mountain boundary.

For each valley \(V=(x_V,y_V)\) with its adjacent vertices \(L=(x_{V-1},y_{V-1})\) (to its left) and \(R=(x_{V+1},y_{V+1})\) (to its right), one may prove that the light source must be placed within an interval given by \[ \left[x_V - \frac{h-y_V}{y_{V-1}-y_V}(x_V-x_{V-1}),\quad x_V + \frac{h-y_V}{y_{V+1}-y_V}(x_{V+1}-x_V)\right] \] so that the line from the light source \((x, h)\) to \(V\) stays above the adjacent peaks. (All inequalities and formulas are in \(\LaTeX\) format.)

Your task is to determine the minimum number of point light sources required such that every valley is illuminated, i.e. each valley has at least one light source placed in its valid interval. If there is no valley, output 0.

inputFormat

The input begins with a line containing two numbers: an odd integer n (the number of vertices) and an integer h (the height of each light source). The following n lines each contain two numbers xi and yi, representing the coordinates of the mountain's vertices in order.

It is guaranteed that the vertices are given in increasing order of x and that for every valley (i.e. for every index \(i\) with \(1 < i y_i\) and \(y_{i+1} > y_i\).

outputFormat

Output a single integer, the minimum number of light sources needed so that every valley is illuminated.

sample

5 25
0 10
2 20
4 5
6 20
8 10

1