You are painting a fence with sections, numbered from
to
. There are
artists, each willing to paint their design on a specific portion of the fence. However, artists will never agree to have their section painted over, so they will only paint their portion of the fence if no one else will paint any part of it.
You want to select a set of painters that does not conflict to minimize the number of unpainted sections.
Input
The first line contains two positive integers
and
.
Each of the next lines contains two positive integers
and
, where
, indicating that the
th artist wants to paint all sections between section
and section
, inclusive.
Output
Print, on a single line, a single integer indicating the minimum number of unpainted sections.
Sample Input
8 3
1 3
2 6
5 8
Sample Output
1
Comments