Skarby

Skarby

Stryjek dał Ci na imieniny mapę skarbów. Jest to dosyć nietypowa mapa, gdyż jest ona wyłącznie listą pozycji i głębokości skarbów pod ziemią. Po zaznaczeniu położenia skarbów na siatce z kwadratowymi polami otrzymałeś właściwą mapę. Chcesz wykopać wszystkie skarby, przekopując jak najmniej pól. Pole o pozycji x i głębokości h można przekopać wyłącznie wtedy, jeśli przekopano wszystkie pola o pozycjach x - 1, x, x + 1 o głębokościach mniejszych od h (mieszczących się na mapie), w przeciwnym wypadku grunt się osunie i zostaniesz zasypany żywcem.

Zadanie:

Napisz program, który:
• wczyta opis mapy
• wyznaczy, ile minimalnie pól trzeba przekopać, aby uzyskać wszystkie skarby
• wypisze wynik na standardowe wyjście

Wejście:

W pierwszej linii znajdują się dwie liczby całkowite: n i s (1 <= n <= 1000000; 1 <= s <= 1000000). Następnie jest s linii, są to położenia skarbów. Jedna linia składa si, z dwóch liczb całkowitych: pozycji x oraz głębokości h (1 <= x <= n; 1 <= h <= 1000000).

Wyjście:

Jedna liczba, będąca minimalną liczbą pól, które trzeba przekopać, aby uzyskać wszystkie skarby.

Przykład:

wejście:
4 4
2 1
1 2
3 2
2 3

wyjście:
8

Wyjaśnienie przykładu:

	1	2	3	4
1		s
2	s		s
3		s
4

Numery wierszy to głębokość (h), a numery kolumn to pozycja (x).
Szare pola są przekopane, s to skarb.