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 |