Problem
Eines Tages, als Strafe für Streiche und Betrug, ließ Tante Polly Tom einen Zaun mit einer Länge von
L Yards streichen. Sie alle erinnern sich perfekt daran, dass Tom seine Arbeit (für verschiedene Nischen) an andere Jungen verkaufte, die den Zaun weiß machen wollten.
Als Tom kein Kalk mehr hatte, konnten die
N Jungen den Zaun bemalen. Und da Tom den Jungs nicht besonders folgte, malte jeder den Teil des Zauns, der ihm am besten gefiel.
Jeder
i Junge fing an, den Zaun von einer vertikalen Tafel mit der Koordinate
Lefti zu streichen, und färbte bis zur Tafel mit der Koordinate
Righti (die Länge der Tafel ist gleich 1).
Bestimmen Sie die Länge des Zauns, den Sie selbst anmalen müssen.
Eingabe
In der ersten Zeile steht die Zahl L - die Länge des Zauns von Tante Polly. In der zweiten Zeile befindet sich die Zahl N, in den folgenden N Zeilen sind Lefti und Righti Paare. Alle Zahlen sind ganze Zahlen
Einschränkungen:
\(0 <= L <= 2 \cdot 10^9\);
\(-10^9 <= Left_i <= Right_i <= 10^9\);
\(1 <= N <= 15 000\).
Ausgabe
Um eine Zahl abzuleiten, ist die Länge des Zauns, die dem Tom übermalt werden muss.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
20
1
10 20
|
10 |
| 2 |
10
1
10 10 |
10 |
| 3 |
100
2
10 30
20 40 |
70 |