시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 512 MB (추가 메모리 없음) | 88 | 71 | 63 | 86.301% |
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 ai and 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.
3 1 1 2 3 2 2
2
8 0 1 1 7 4 8 3 7 1 2 4 5 3 7 1 8
-1