Description

There is a mountain with ups and downs. It can be modeled as a polygon consisting of $n$ points $(x_i, y_i)$ (where $n$ is odd), plus the two points $(x_1, -\inf)$ and $(x_n, -\inf)$.

For every integer $i$ satisfying $i \neq 1$, $i \neq n$, and $i \bmod 2 = 1$, the point $(x_i, y_i)$ is a valley.

Now we want to place some point light sources at height $h$, so that all valleys are illuminated, meaning the line segment connecting a light source and a valley does not pass through the interior of the mountain.

Find the minimum number of light sources needed.

Input Format

The first line contains integers $n, h$.

The next $n$ lines each contain integers $x_i, y_i$.

It is guaranteed that $x_1 < x_2 < \cdots < x_n$ and $y_1 < y_2, y_2 > y_3, y_3 < y_4, \cdots, y_{n-1} > y_n$.</p>

Output Format

Output the minimum number of light sources needed.

9 6
0 0
1 2
3 0
6 3
8 1
9 2
11 1
12 4
14 0

1

9 5
-5 2
-4 3
-2 1
0 4
2 2
3 3
4 1
5 2
6 1

2

Hint

Illustration for Sample 1

Illustration for Sample 2

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata: $3 \le n < 10^6$, $n \bmod 2 = 1$, $1 \le h \le 10^6$, $-10^6 \le x_i \le 10^6$, $0 \le y_i < h$, $x_1 < x_2 < \cdots < x_n$, and $y_1 < y_2, y_2 > y_3, y_3 < y_4, \cdots, y_{n-1} > y_n$.</p>

Notes

The scoring of this problem follows the original COCI problem, with a full score of $110$.

Translated from COCI2020-2021 CONTEST #5 T4 Planine.

Translated by ChatGPT 5