Problem
Pada suatu hari, sebagai hukuman untuk gurauan dan penipuan, Mak Cik Polly membuatkan Tom mengecat pagar halaman
L. Anda semua masih ingat bahawa Tom menjual (untuk pelbagai barangan) hasil kerjanya kepada budak lain yang ingin mengapur pagar.
Apabila Tom kehabisan kapur, pagar telah dicat oleh budak lelaki
N. Dan memandangkan Tom tidak betul-betul mengikut budak lelaki itu, semua orang melukis bahagian pagar yang paling dia suka.
Setiap budak lelaki
i-mula melukis pagar dari papan menegak dengan koordinat
Kirii dan melukis hingga papan dengan koordinat
Kanan< sub>i (panjang papan dianggap sama dengan 1).
Tentukan panjang pagar yang Tom perlu cat sendiri.
Input
Baris pertama mengandungi nombor L - panjang pagar Mak Cik Polly. Barisan kedua mengandungi nombor N, baris N seterusnya - berpasangan Kiri< sub>i< /sub> dan Righti. Semua nombor adalah integer
Sekatan:
\(0 <= L <= 2 \cdot 10^9\);
\(-10^9 <= Kiri_i <= Kanan_i <= 10^9\);
\(1 <= N <= 15 000\).
Cetakan
Cetak satu nombor - panjang pagar yang Tom perlukan untuk menyelesaikan lukisan.
Contoh
| # |
Input |
Output |
| 1 |
20
1
10 20
|
10 |
| 2 |
10
1
10 10
| 10 |
| 3 |
100
2
10 30
20 40
| 70 |