## ICPC PACNW 2016 H - Paint

View as PDF

Points: 7
Time limit: 1.8s
Memory limit: 256M

Problem type
Allowed languages
C, C++, Java, Python

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