يدير Farmer John مزرعته بموثوقية في كل شيء إلا جز العشب في وقته. لا يحرك آلة الجز إلا مرة يوميًا. يبدأ اليوم1 من $(x_1, y_1)$، وفي اليوم $d$ يجز على مقطع مستقيم إلى $(x_d, y_d)$ أفقيًا أو عموديًا على الخريطة الثنائية الأبعاد: $x_d = x_{d-1}$ أو $y_d = y_{d-1}$. يتناوب الاتجاهان في الأيام المتتالية.

تقدمه بطيء لدرجة أن العشب قد ينمو قبل انتهاء الجز. ما جُز في اليوم $d$ يعود في اليوم $d + T$. فإذا تقاطع المسار مع مسار جُز قبل $T$ أيام على الأقل، يجُز النقطة نفسها ثانية. يريد عد هذه الحالات لتحسين استراتيجيته السيئة.

عد تقاطعات المسار مع مقاطع سابقة نما عشبها مجددًا. احسب فقط التقاطعات «المتعامدة»: نقطة مشتركة بين مقطع أفقي وعمودي ليست طرفًا لأي منهما.

الإدخال

يحتوي السطر الأول على $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 ثوان لكل حالة (10 لـ Python وJava)، وذاكرة512 MB.

مؤلفا المسألة: Chad Waters وBrian Dean