광고

어느 공원의 인기 있는 조깅 코스를 따라 광고판(광고를 붙이는 특수한 표지판)이 일정한 간격으로 세워져 있다. 광고판에는 코스를 따라 놓인 순서대로 연속된 정수 번호가 매겨져 있으며, 각 광고판에는 광고를 최대 한 개만 붙일 수 있다.

한 광고주는 모든 조깅하는 사람이 코스를 달리는 동안 자신의 광고를 최소 $K$번 보도록 하고 싶다. 각 사람은 매일 같은 구간을 달리며, 광고주에게 중요한 것은 그 사람이 지나치며 보는 광고판뿐이므로, 각 사람의 달리기는 처음 본 광고판 번호와 마지막으로 본 광고판 번호로 나타낼 수 있다. 처음에 $A$번, 마지막에 $B$번 광고판을 보는 사람은 $A$번, $B$번, 그리고 그 사이의 모든 광고판을 본다.

그런데 일부 사람은 충분히 멀리 달리지 못해 광고판을 $K$개나 지나가지는 못한다. 그런 사람에게는 광고를 $K$번 보여 줄 수 없으므로, 광고주는 대신 그 사람이 지나는 구간의 모든 광고판에 광고가 붙어 있기를 요구한다. 이것이 할 수 있는 최선이며 광고주를 만족시킨다.

정리하면, 어떤 사람이 지나는 구간에 광고판이 $L$개 있을 때 광고주는 그중 최소 $\min(K, L)$개의 광고판에 광고가 붙어 있기를 요구한다. 모든 사람의 요구를 만족시키기 위해 광고를 붙여야 하는 광고판의 최소 개수를 구하여라.

첫째 줄에 두 정수 $K$와 $N$ ($1 \le K, N \le 1000$)이 공백으로 구분되어 주어진다. $K$는 모든 사람이 보아야 하는 광고의 최소 개수이고, $N$은 사람의 수이다.

이어지는 $N$개의 줄에는 각각 두 정수 $A_i$와 $B_i$ ($|A_i|, |B_i| \le 10000$)가 주어진다. 이는 $i$번째 사람이 처음과 마지막으로 본 광고판 번호이다. 두 수는 순서에 상관없이 주어질 수 있으며, $i$번째 사람은 $A_i$번, $B_i$번, 그리고 그 사이의 모든 광고판을 본다.

모든 사람의 요구를 만족시키기 위해 광고를 붙여야 하는 광고판의 최소 개수를 나타내는 정수 하나를 출력한다.