Under construction

Still being built. Things may change

Liars

Interview

Time limit1sMemory limit512 MB

Summary
Given each person's claimed range for the truth-teller count, find the maximum possible number of truth-tellers within any consistent assignment.
Level

Medium6 of 10

Topics
Hash map, Prefix sum, Implementation
Solved
No attempts yet

Problem

There are n people in a circle, numbered from 1 to n. Each person always tells the truth or always lies.

Each person i makes the claim: "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.

Input

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)

Output

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.

Examples2

  1. Example 1

    Input
    3
1 1
2 3
2 2
    Expected output
    2

  2. Example 2

    Input
    8
0 1
1 7
4 8
3 7
1 2
4 5
3 7
1 8
    Expected output
    -1