题目描述

农民约翰在管理农场的各个方面都相当可靠，除了一点：他不善于及时割草。

事实上，他每天只能移动割草机一次。

在第$\red{1}$天，他从位置$\red{（x1，}$$\red{y1）}$开始，在第$\red{d}$天，他沿着直线段割草到位置$\red{（xd，}$$\red{yd）}$ ，在农场的$\red{2D}$地图上水平或垂直移动；

也就是说$\red{xd=xd-1 }$或者 $\red{yd=yd-1. FJ}$连续几天在水平和垂直移动之间交替。

$\red{FJ}$的进度如此缓慢，以至于在他完成所有割草之前，他割草的一些草可能会长回来。

在第$\red{d}$天割草的任何部分都会在第$\red{d+T}$天再次出现，因此，如果$\red{FJ}$的割草路径与他至少提前$\red{T}$天割草的路径相交，他将再次在同一点割草。

为了尝试改革他糟糕的割草策略，$\red{FJ}$想统计一下这种情况发生的次数。

请计算$\red{FJ}$的割草路径穿过草已经长回来的早期部分的次数。

您应该只计算"垂直"交叉点，即水平段和垂直段之间的公共点，这两个段都不是终点。

输入格式

第一行输入包含$\red{N(2≤}$$\red{N≤}$$\red{100,000)}$ 并且$\red{ T (1≤}$$\red{T≤}$$\red{N).}$

接下来的$\red{N}$行描述了割草机在第$\red{1…}$$\red{N}$天的位置。

这些 行的第$\red{i}$行包含整数$\red{xi}$和$\red{yi}$（每个非负整数最多$\red{100000000}$）。

输出格式

请输出上述交叉点数量的计数，其中$\red{FJ}$重新切割了先前切割后重新生长的草点。

样例

输入样例

7 4
0 10
10 10
10 5
3 5
3 12
6 12
6 3

输出样例

1

提示

在这里，$\red{FJ}$在第$\red{7}$天穿过他在第$\red{2}$天割下的一段草，这很重要。

其他十字路口不计算在内。

注意：这个问题扩展了限制：每个测试用例$\red{5}$秒（$\red{Python}$和$\red{Java}$为$\red{10}$秒），内存$\red{512 MB}$。