시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 512 MB (언어별 추가 메모리 없음) 5 5 4 100.000%

문제

There are n people in a circle, numbered from 1 to n, each of whom always tells the truth or always lies.

Each person i makes a claim of the form: “the number of truth-tellers in this circle is between aand bi, inclusive.”

Compute the maximum number of people who could be telling the truth.

입력

The first line contains a single integer n (1 ≤ n ≤ 103). Each of the next n lines contains two space-separated integers ai and bi (0 ≤ ai ≤ bi ≤ n).

출력

Print, on a single line, the maximum number of people who could be telling the truth. If the given set of statements is inconsistent, print -1 instead.

예제 입력 1

3
1 1
2 3
2 2

예제 출력 1

2

예제 입력 2

8
0 1
1 7
4 8
3 7
1 2
4 5
3 7
1 8

예제 출력 2

-1