Farmer John は農場管理のあらゆる面で頼れますが、草を適時に刈ることだけは苦手です。実際、草刈り機を1日1回しか動かせません。1日目は $(x_1, y_1)$ から始め、第 $d$ 日に直線に沿って $(x_d, y_d)$ まで刈ります。2次元地図上で水平または垂直に動き、$x_d = x_{d-1}$ または $y_d = y_{d-1}$ です。連続する日では水平移動と垂直移動が交互になります。

進み方が遅いため、全て刈り終える前に刈った草がまた伸びることがあります。第 $d$ 日に刈った草は第 $d + T$ 日に復活するので、少なくとも $T$ 日前に刈った経路と交差すると同じ場所を再び刈ります。悪い戦略を改善するため、その回数を数えたいのです。

経路が、草が復活した以前の線分と交差する回数を数えてください。数えるのは「直交する」交差だけです。水平線分と垂直線分の共通点で、どちらの端点でもない点と定義します。

入力

1行目は $N$（$2 \leq N \leq 100,000$）と $T$（$1 \leq T \leq N$、$T$ は偶数）です。

続く $N$ 行は第 $1 \ldots N$ 日の草刈り機の位置です。第 $i$ 行には整数 $x_i$ と $y_i$ があり、ともに $1,000,000,000$ 以下の非負整数です。

出力

以前刈られて復活した草を再び刈る、上記の交点数を出力してください。

入出力例

入力 1

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

出力 1

1

注記

7日目に2日目の線分と交差し、これは数えます。他の交差は数えません。

説明：この問題の制限は拡大され、各テストケース5秒（Python と Java は10秒）、メモリ512 MBです。

問題作成：Chad Waters と Brian Dean