AIOC Banner

Problem: Vitamin D

Want to try solving this problem? You can submit your code online if you log in or register.


Vitamin D

Time Limit: 1 second
Memory Limit: 128 MB
Input File: standard input
Output File: standard output

After spending all night coding solutions to informatics problems, Nicole is keen to get some vitamin D: by relaxing in a nice, sunny spot on the beach.

Unfortunately due to the Earth's rotation and cloud movements, the sun is not so consistent in where it chooses to shine on the beach. Specifically, for each minute i, the sun shines brightly on the section of beach that is between ai and bi metres from the left end of the beach (ai < bi). Everywhere else on the beach during that minute is unbearably cold - so cold that Nicole can not possibly sit there during that minute.

Nicole has already calculated from Bureau of Meterology data where the sunny section of the beach will be for each of the following N minutes (after which she must leave for a hackathon). Your task is to develop an algorithm that will determine the best spot for her to soak up vitamin D and when to sit there.

Nicole wants to sit in the sun for as long as possible without having to move. Therefore, your program must find the longest period of time during which there exists a spot on the beach that is in sunlight for this whole period (that is, there is no minute during this period in which the spot is not sunlit). Note that a "spot" to sit must be at least one metre wide, so for Nicole to sit x metres along the beach, the one-metre section between x and x+1 must be sunny.

Input

Output

Output should consist of one line containing one integer: the maximum number of consecutive minutes during which Nicole can sit in some sunny spot on the beach.

Sample Input

5 10
6 10
0 6
5 8
1 9
1 5

Sample Output

3

Explanation

Nicole can sit 5 metres from the left end of the beach (between 5m and 6m) from the end of the first minute to the end of the fourth minute. There is no spot that is continuously sunny for longer than 3 minutes.

Subtasks

 


Privacy statement
© Australian Mathematics Trust 2001-2021

Contact: training@orac.amt.edu.au
Page generated: 21 September 2021,  9:11am AEST