MAFIA - Who is Mafia

Anton and Brahle are playing Mafia among other players. Anton is claiming that he is a policeman and presents a list of N statements in form of : There is at least one Mafia member in interval [a, b]. However Brahle is wary of Anton's true alignment, deducted from previous experiences, hence he is suspecting Anton might be working for the Mafia. To help Brahle you must answer what is minimal number of Mafia members must be in the game that Anton's claims could be true.

Input

In the first line there is the number N <= 20 and afterwards N lines containing numbers a and b described in problem description (1 <= a <= b <= 10^9)

Output

You are to write minimal number of Mafia members in the game which could be positioned at will so that Anton's claim is true.

Example

Input:
2 
2 9 
5 29 

Output:
1

If we position Mafia member on any position between 5th and 9th spot inclusive Anton's claim is true and that is minimal number of Mafia members required


Added by:nmiculinic
Date:2013-01-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.