Description

There is a row of trees along a road of length $l$ outside a school's main gate. The distance between any two adjacent trees is $1$ meter. We can regard the road as a number line, with one end at position $0$ and the other end at $l$. At every integer point on the number line, namely $0, 1, 2, \dots, l$, there is a tree.

Some regions of the road will be used for building a subway. Each region is represented by its starting point and ending point on the number line. It is known that the coordinates of the starting and ending points of any region are integers, and different regions may overlap. All trees within these regions (including the two trees at the endpoints of each region) will be removed. Your task is to compute how many trees remain on the road after removing these trees.

Input Format

The first line contains two integers, representing the road length $l$ and the number of regions $m$.

The next $m$ lines each contain two integers $u, v$, representing the starting point and ending point of a region.

Output Format

Output a single integer on one line, representing the number of trees remaining on the road after the removal.

500 3
150 300
100 200
470 471

298

Hint

• Constraints:

  • For 20% of the testdata, the regions are guaranteed to be non-overlapping.
  • For 100% of the testdata, $1 \leq l \leq 10^4$, $1 \leq m \leq 100$, $0 \leq u \leq v \leq l$.

• Source: NOIP 2005 Junior - Problem 2.

Translated by ChatGPT 5