거짓말쟁이
면접 대비시간 제한1초메모리 제한512 MB
각 사람이 진실한 사람 수의 범위를 주장할 때 모순 없이 참인 사람의 수를 최대로 구합니다.
문제
원 위에 n명의 사람이 있고 1번부터 n번까지 번호가 붙어 있다. 각 사람은 항상 진실만을 말하거나 항상 거짓말만 한다.
각 사람 i는 "이 원 안에서 진실을 말하는 사람의 수는 ai 이상 bi 이하이다"라는 주장을 한다.
진실을 말하고 있을 수 있는 사람 수의 최댓값을 구하시오.
입력
첫째 줄에 정수 n이 주어진다. (1 ≤ n ≤ 103)
다음 n개의 줄에 각각 두 정수 ai와 bi가 공백으로 구분되어 주어진다. (0 ≤ ai ≤ bi ≤ n)
출력
진실을 말하고 있을 수 있는 사람 수의 최댓값을 한 줄에 출력한다.
주어진 주장들이 서로 모순이면 -1을 출력한다.