URI Online Judge | 1234

The Philosopher's Stone

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

The Federal University of Southern Border (in Portuguese: Universidade Federal da Fronteira Sul, or shortly UFFS) was created in September 9, 2009, having its activities of research, extension and teaching started in March 29, 2010, in rented temporary buildings. Nowadays, the University has 6 campi, in the cities of: Chapecó, Laranjeiras do Sul, Realeza, Cerro Largo, Erechim and Passo Fundo. In Chapecó, the moving from the temporary building to the campus happened in the 2nd semester of 2013.

In the temporary building in which was sited the course of Computer Science were also sited many other undergraduate courses, like the course of Defence against the Dark Arts, but there were only 3 labs, 2 auditoria and 1 philosopher's stone. All the researchers interested in using the philosopher's stone needed to make their requests at least one week earlier. Based on the list of requests made for the week, the secretary could decide which requests should be attended in order to minimise the amount of time in which the philosopher's stone would be unused. The philosopher's stone was available for use 12 hours by day, which corresponds to 3,600 minutes by week. Enumerating then these 3,600 minutes by 1 to 3,600, each researcher, while making the request, should inform the minute from which the researcher would like to start using the philosopher's stone and the minute from which the philosopher's stone would be available for being used by another researcher.

Write a program to manage the requests as described. We will be in charge of coming back in time to deliver your program to the secretary.

Input

The first line of the input consists of a single integer N (1 ≤ N ≤ 103), which represents the number of requests that have been made for the week. Each one of the N next lines, in turn, describes a request by two integers i and j (1 ≤ i < j ≤ 3,600), which represent respectively the minute from which the researcher would like to start using the philosopher's stone and the minute from which the philosopher's stone would be available for being used by another researcher.

Output

Print a single line containing the maximum number of minutes of the week in which it is possible not to leave the philosopher's stone unused.

Input Samples Output Samples

5
1 1200
960 2880
3360 3600
1680 2160
2640 3600

2639

6
1 240
240 960
2400 2880
3120 3360
720 1440
2640 3360

1679