Problem
Un giorno, come punizione per scherzi e inganni, zia Polly ha fatto dipingere a Tom una staccionata a
L cortile. Tutti voi ricordate molto bene che Tom vendette (per varie chicche) il suo lavoro ad altri ragazzi che volevano imbiancare la staccionata.
Quando Tom ha finito la calce, la recinzione era stata dipinta da
N ragazzi. E siccome Tom non seguiva davvero i ragazzi, ognuno ha dipinto la parte della recinzione che gli piaceva di più.
Ogni
i-esimo ragazzo ha iniziato a dipingere la recinzione da un'asse verticale con coordinata
Sinistrai e l'ha dipinta su un'asse con coordinata
Destra< sub>i (la lunghezza della tavola è considerata pari a 1).
Determina la lunghezza della recinzione che Tom dovrà dipingere da solo.
Input
La prima riga contiene il numero L - la lunghezza del recinto di zia Polly. La seconda riga contiene il numero N, le successive N righe - coppie Sinistra< sub>i< /sub> e Destrai. Tutti i numeri sono numeri interi
Restrizioni:
\(0 <= L <= 2 \cdot 10^9\);
\(-10^9 <= I_sinistra <= I_destra <= 10^9\);
\(1 <= N <= 15 000\).
Impressum
Stampa un singolo numero: la lunghezza della recinzione di cui Tom ha bisogno per finire di dipingere.
Esempi
| # |
Input |
Uscita |
| 1 |
20
1
10 20
|
10 |
| 2 |
10
1
10 10
| 10 |
| 3 |
100
2
10 30
20 40
| 70 |