진실을 말하라
면접 대비시간 제한2초메모리 제한512 MB
각 사람이 진실자의 수가 [a,b] 범위에 있다고 주장할 때 가능한 진실자의 최댓값을 구하고 불가능하면 -1을 출력합니다.
문제
방 안에 n명의 사람이 있다. 각 사람은 항상 진실만을 말하거나 항상 거짓만을 말한다. 각 사람은 "우리 중 a명 이상 b명 이하가 진실을 말하고 있다"라는 형태의 주장을 한다. 방 안에서 진실을 말하는 사람의 최대 수는 얼마인가?
입력
각 입력은 하나의 테스트 케이스로 이루어진다. 프로그램이 서로 다른 입력에 대해 여러 번 실행될 수 있다.
각 테스트 케이스의 첫 줄에는 방 안의 사람 수를 나타내는 정수 n (1 ≤ n ≤ 1,000)이 주어진다.
다음 n개 줄에는 각각 공백으로 구분된 두 정수 a와 b (0 ≤ a ≤ b ≤ n)가 주어진다. 각 줄은 한 사람의 "우리 중 a명 이상 b명 이하가 진실을 말하고 있다"라는 주장을 나타낸다.
출력
진실을 말하는 사람의 최대 수를 하나의 정수로 출력한다. 주장들이 서로 모순되면 -1을 출력한다.