توجد شبكة بحجم $N \times M$. خليتها العلوية اليسرى هي $(1,1)$ والسفلية اليمنى هي $(N,M)$. وتوجد أرضية لا ينفذ الماء خلالها مباشرة أسفل الصف الأخير.

كل خلية مسدودة أو مفتوحة، ولا ينفذ الماء عبر الخلايا المسدودة. في كل عمود، إما لا توجد خلايا مسدودة، أو تشكل جميعها كتلة متصلة متتالية. ولا يمر الماء بين خليتين مسدودتين متجاورتين. تسمى الكتلة التي تحتوي على خلية من الصف الأخير متصلة بالأرضية، وتسمى أي كتلة أخرى عائمة.

تندمج كتلتان في عمودين متجاورين إذا احتوتا على خليتين في الصف نفسه. ولا ينفذ الماء عبر الحد الرأسي المشترك بينهما أيضًا. وينطبق هذا الدمج على جميع الأعمدة المتتالية. لن تحدث حالة تستلزم دمج كتلة متصلة بالأرضية مع كتلة عائمة، كما في العمودين الثاني والثالث بالشكل؛ فالكتلتان المندمجتان إما متصلتان بالأرضية معًا أو عائمتان معًا. ولن تحدث حالة تلامس كتلتين عند رأس واحد فقط، كما في العمودين الخامس والسادس.

مثلًا، يوضح الشكل التالي شبكة بحجم $8 \times 12$. في العمود الأول تسد الخلايا من الصف $6$ إلى $8$، ولا توجد خلايا مسدودة في العمود الثاني، وفي الثالث تسد الخلايا من الصف $5$ إلى $8$.

لنفترض صب ماء كافٍ من الأعلى. يتجمع الماء في الخلايا الموسومة $1$، وكذلك الموسومة $2$. ويتجمع أيضًا في المنطقتين $3$ و$4$. يجب الانتباه هنا: نفترض عدم وجود هواء، لذا تمتلئ المنطقة $4$ إلى الارتفاع نفسه للمنطقة $3$. (ويكافئ ذلك افتراض أن الهواء ينفذ عبر كل شيء.) توضح المنطقة $5$ تجمع الماء فوق كتلة عائمة. لاحظ أن الماء لا يتجمع في حالات مثل المنطقة $6$.

اكتب برنامجًا يقرأ توزيع الخلايا ويطبع عدد الخلايا التي تحتفظ بالماء بعد صب كمية كافية منه.

الإدخال

الإدخال القياسي بالشكل التالي. يحتوي السطر الأول على عددين صحيحين $N,M$ ($1 \le N,M \le 100{,}000$). ويحتوي كل سطر من الأسطر التالية وعددها $M$ على عددين صحيحين $A,B$ ($1 \le A \le B \le N$)، لوصف الأعمدة من اليسار إلى اليمين: تكون الخلايا المسدودة من الصف $A$ إلى الصف $B$. وفي الحالة الخاصة التي لا توجد فيها خلايا مسدودة في العمود، تكون كل من $A$ و$B$ مساوية لـ $0$.

الإخراج

اطبع على الإخراج القياسي عدد خلايا الشبكة التي تحتفظ بالماء بعد صب كمية كافية منه.

المهام الفرعية

• المهمة الفرعية 1: $7$ من أصل $100$ نقطة. لا توجد خلايا مسدودة إلا في العمود الأول والأخير.
• المهمة الفرعية 2: $18$ من أصل $100$ نقطة. إذا احتوى عمود على خلايا مسدودة، فكتلته متصلة بالأرضية.
• المهمة الفرعية 3: $28$ من أصل $100$ نقطة. $1 \le N,M \le 1{,}000$.
• المهمة الفرعية 4: $47$ من أصل $100$ نقطة. لا توجد قيود إضافية.

أمثلة

الإدخال 1

8 12
6 8
0 0
5 8
7 8
5 8
0 0
1 6
2 2
1 6
0 0
5 8
0 0

الإخراج 1

22