## Light Bulbs

View as PDF

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

Author:
Problem type

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

#### Input Specification

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

The next lines contains and , the -th line describing the lamplighter moving at the -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 minute.

#### Sample Input

6 4
1 4
3 5
2 6
3 4

#### Sample Output

3

#### 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.