题目描述

译自 COCI 2020/2021 Contest #5 T4「Planine」

定义山为由 $n$（$n$ 是奇数）个点 $(x_i,y_i)$ 以及 $(x_1,-\infty)$，$(x_n,-\infty)$ 组成的多边形。

定义山谷是这 $n$ 个点中的 $(x_i,y_i)$，要求 $i \ne 1$，$i \ne n$，$i \equiv 1 \pmod{2}$。

现您想在 $y = h$ 这条直线上放上一些点光源，使得所有的山谷都被照亮，照亮的条件是：从某个点光源连一条线段到山谷，这条线段不穿过山内部。

鉴于点光源是要钱的，您需要求出最少需要的点光源个数。

输入格式

第一行两个整数 $n, h$。

接下来 $n$ 行，一行两个整数 $(x_i, y_i)$。

输出格式

仅一行一个整数，表示最少需要的点光源个数。

样例 1

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

text

输出 1

text

样例 2

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

text

输出 2

text

数据范围与提示

对于所有子任务，有：

• $3 \le n < 10^6$
• $n \equiv 1 \pmod{2}$
• $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$
• $y_1 < y_2, y_2 > y_3, y_3 < y_4, \ldots, y_{n-1} > y_n$（即相邻点纵坐标大小交替）</li> </ul>

  子任务编号	特殊限制	分值
  1	$y_2 = y_4 = \cdots = y_{n-1}$	$20/110$
  2	$n < 2 \times 10^3$	$30/110$
  3	无	$60/110$