Light Bulbs

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type

Back in the day, lamplighters turned on your street lights! In this peculiar city, there are N street lights numbered 1 to N. Every minute, one lamplighter would walk from L_i-th to R_i-th street lamp (inclusive), turning them all on. How many full minutes will it take for all of the street lights to turn on?


1\le N\le 1000

1\le M\le 2000

1\le L_i\le R_i\le N

Input Specification

The first line contains N and M, the number of street lamps and the number of minutes to consider.

The next M lines contains L_i and R_i, the j-th line describing the lamplighter moving at the j-th minute.

Output Specification

One integer, the number of full minutes before all of the street lights are turned on. It is guaranteed that all of the street lights will be turned on by the M minute.

Sample Input

6 4
1 4
3 5
2 6
3 4

Sample Output


Sample Explanation

In the first two minutes, the sixth lamp isn't turned on. However, once the third minute completes, the ranges 1 4, 3 5 and 2 6 are covered, which covers all of the lamps from 1 to 6. So, it'll take 3 minutes.


There are no comments at the moment.