Problem
یک روز، به عنوان مجازات برای شوخی و فریب، عمه پولی تام را مجبور کرد یک حصار حیاط
L بکشد. همه شما به خوبی به یاد دارید که تام (برای چیزهای مختلف) کار خود را به پسران دیگری که می خواستند حصار را سفید کنند فروخت.
زمانی که آهک تام تمام شد، حصار توسط پسران
N رنگ شده بود. و از آنجایی که تام واقعاً از پسرها پیروی نمی کرد، همه قسمتی از حصار را که بیشتر دوست داشت نقاشی کردند.
هر پسر
i-ام شروع به رنگ آمیزی حصار از یک تخته عمودی با مختصات
چپi کرد و با مختصات
راست< تا تخته نقاشی کرد. sub>i (طول برد برابر با 1 در نظر گرفته می شود).
طول حصاری را که تام برای رنگ آمیزی نیاز دارد تعیین کنید.
ورودی
خط اول شامل عدد L - طول حصار عمه پولی است. خط دوم شامل شماره N، خط N بعدی - جفت چپ< sub>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 |