16689번 - Liars 다국어

문제

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 a_i and b_i, inclusive.”

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

입력

The first line contains a single integer n (1 ≤ n ≤ 10³). Each of the next n lines contains two space-separated integers a_i and b_i (0 ≤ a_i ≤ b_i ≤ 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.

제한

힌트