Problem
एक दिन, शरारतों और छल की सजा के रूप में, आंटी पोली ने टॉम को एक
L यार्ड की बाड़ पेंट कराया। आप सभी को अच्छी तरह याद है कि टॉम ने (विभिन्न उपहारों के लिए) अपना काम दूसरे लड़कों को बेच दिया था जो बाड़ को सफेद करना चाहते थे।
जब तक टॉम का चूना खत्म हो गया, तब तक बाड़
N लड़कों द्वारा रंगा जा चुका था। और चूंकि टॉम वास्तव में लड़कों का अनुसरण नहीं करता था, इसलिए सभी ने बाड़ के उस हिस्से को चित्रित किया जो उसे सबसे अच्छा लगा।
प्रत्येक
i-वें लड़के ने निर्देशांक
Lefti के साथ एक लंबवत फलक से बाड़ को पेंट करना शुरू किया और
दाएं<कोड> समन्वय के साथ तख्ते तक पेंट किया उप>i (बोर्ड की लंबाई 1 के बराबर मानी जाती है)।
बाड़ की लंबाई निर्धारित करें जिसे टॉम को खुद पेंट करने की आवश्यकता होगी।
इनपुट
पहली पंक्ति में संख्या L - आंटी पोली की बाड़ की लंबाई शामिल है। दूसरी पंक्ति में संख्या N है, अगली N पंक्तियां - जोड़े बाएं< उप>i< /sub> और दाएंi। सभी संख्याएँ पूर्णांक हैं
प्रतिबंध:
\(0 <= L <= 2 \cdot 10^9\);
\(-10^9 <= Left_i <= Right_i <= 10^9\);
\(1 <= N <= 15 000\)।
छाप
एक संख्या प्रिंट करें - बाड़ की लंबाई जिसे टॉम को पेंटिंग खत्म करने के लिए चाहिए।
उदाहरण
<टेबल क्लास = "टेबल-एसएम टेबल-बॉर्डर टेबल-स्ट्राइप्ड टेबल-लिस्ट-टेस्ट">
<सिर>
<थ वर्ग = "अंक"> #
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
<टीडी>
20
1
10 20
10 |
| 2 |
10
1
10 10
| 10 |
| 3 |
100
2
10 30
20 40
| 70 |