Problem
Um dia, como punição por pegadinhas e trapaças, tia Polly fez Tom pintar uma cerca de quintal
L. Todos vocês se lembram muito bem que Tom vendeu (por vários brindes) seu trabalho para outros meninos que queriam caiar a cerca.
Quando Tom ficou sem cal, a cerca já havia sido pintada por
N meninos. E como Tom não acompanhava muito os meninos, cada um pintou a parte da cerca que mais gostou.
Cada menino
i começou a pintar a cerca de uma prancha vertical com a coordenada
Esquerdai e pintou a prancha com a coordenada
Direita< sub>i (o comprimento da placa é considerado igual a 1).
Determine o comprimento da cerca que Tom precisará pintar sozinho.
Entrada
A primeira linha contém o número L - o comprimento da cerca da Tia Polly. A segunda linha contém o número N, as próximas N linhas - pares Esquerda< sub>i e Direitai. Todos os números são inteiros
Restrições:
\(0 <= L <= 2 \cdot 10^9\);
\(-10^9 <= Left_i <= Right_i <= 10^9\);
\(1 <= N <= 15 000\).
Impressão
Imprima um único número - o comprimento da cerca que Tom precisa para terminar de pintar.
Exemplos
| # |
Entrada |
Saída |
| 1 |
20
1
10 20
|
10 |
| 2 |
10
1
10 10
| 10 |
| 3 |
100
2
10 30
20 40
| 70 |