#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);
typedef pair<int, int> pii;

map<pii, int> a;

void ass(bool ex) {
    if (!ex) {
        cout << -1 << '\n';
        exit(0);
    }
}

pii operator+(pii a, pii b) {
    return pii{a.first + b.first, a.second + b.second};
}

pii operator-(pii a, pii b) {
    return pii{a.first - b.first, a.second - b.second};
}

pii nx(pii a) {
    return a + pii{1, -1};
}

int main() {
    #ifdef LOCAL
    assert(freopen("a.in", "r", stdin));
    #else
    #endif
    int n;
    cin >> n;
    int d;
    forn (i, n) {
        int x, y;
        cin >> x >> y;
        if (i == 0) {
            ass(x == 0);
            d = y;
        }
        if (i == 1)
            ass(y == 0 && d == x);
        ass(x + y >= d);
        ass(x >= 0 && y >= 0);
        if (i != 0)
            ass(x != 0);
        if (i != 1)
            ass(y != 0);
        a[pii(x, y)]++;
    }
    for (auto p: a) {
        auto c = p.first;
        if (c.second != 0)
            ass(a.count(c + pii(0, -1)) || a.count(c + pii(-1, -1)) || a.count(c + pii(1, -1)));
        if (c.first != 0)
            ass(a.count(c + pii(-1, 0)) || a.count(c + pii(-1, -1)) || a.count(c + pii(-1, 1)));
    }
    //cerr << "YES\n";
    vector<pair<pii, int>> v;
    for (auto A: a)
        v.push_back(A);
    sort(v.begin(), v.end(), [](pair<pii, int> a, pair<pii, int> b) {
                int sa = a.first.first + a.first.second;
                int sb = b.first.first + b.first.second;
                if (sa != sb)
                    return sa < sb;
                return a.first < b.first;
            });
    int res = 2 * n - 2;

    int carry = 0;
    forn (ii, sz(v)) {
        auto c = v[ii].first;
        int cnt = v[ii].second;
        carry = min(carry, cnt);
        if (a.count(c + pii{-1, -1})) {
            int k = cnt - carry;
            res -= k;
            cnt -= k;
        }
        res -= carry;
        if (ii + 1 < sz(v) && v[ii + 1].first == nx(c))
            carry = cnt;
        else
            carry = 0;
    }
    cout << res << '\n';
}

### Prompt

Please formulate a cpp solution to the following problem:

There is an undirected connected graph with N vertices numbered 1 through N. The lengths of all edges in this graph are 1. It is known that for each i (1≦i≦N), the distance between vertex 1 and vertex i is A_i, and the distance between vertex 2 and vertex i is B_i. Determine whether there exists such a graph. If it exists, find the minimum possible number of edges in it.

Constraints

* 2≦N≦10^5
* 0≦A_i,B_i≦N-1

Input

The input is given from Standard Input in the following format:


N
A_1 B_1
A_2 B_2
:
A_N B_N


Output

If there exists a graph satisfying the conditions, print the minimum possible number of edges in such a graph. Otherwise, print `-1`.

Examples

Input

4
0 1
1 0
1 1
2 1


Output

4


Input

3
0 1
1 0
2 2


Output

-1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);
typedef pair<int, int> pii;

map<pii, int> a;

void ass(bool ex) {
    if (!ex) {
        cout << -1 << '\n';
        exit(0);
    }
}

pii operator+(pii a, pii b) {
    return pii{a.first + b.first, a.second + b.second};
}

pii operator-(pii a, pii b) {
    return pii{a.first - b.first, a.second - b.second};
}

pii nx(pii a) {
    return a + pii{1, -1};
}

int main() {
    #ifdef LOCAL
    assert(freopen("a.in", "r", stdin));
    #else
    #endif
    int n;
    cin >> n;
    int d;
    forn (i, n) {
        int x, y;
        cin >> x >> y;
        if (i == 0) {
            ass(x == 0);
            d = y;
        }
        if (i == 1)
            ass(y == 0 && d == x);
        ass(x + y >= d);
        ass(x >= 0 && y >= 0);
        if (i != 0)
            ass(x != 0);
        if (i != 1)
            ass(y != 0);
        a[pii(x, y)]++;
    }
    for (auto p: a) {
        auto c = p.first;
        if (c.second != 0)
            ass(a.count(c + pii(0, -1)) || a.count(c + pii(-1, -1)) || a.count(c + pii(1, -1)));
        if (c.first != 0)
            ass(a.count(c + pii(-1, 0)) || a.count(c + pii(-1, -1)) || a.count(c + pii(-1, 1)));
    }
    //cerr << "YES\n";
    vector<pair<pii, int>> v;
    for (auto A: a)
        v.push_back(A);
    sort(v.begin(), v.end(), [](pair<pii, int> a, pair<pii, int> b) {
                int sa = a.first.first + a.first.second;
                int sb = b.first.first + b.first.second;
                if (sa != sb)
                    return sa < sb;
                return a.first < b.first;
            });
    int res = 2 * n - 2;

    int carry = 0;
    forn (ii, sz(v)) {
        auto c = v[ii].first;
        int cnt = v[ii].second;
        carry = min(carry, cnt);
        if (a.count(c + pii{-1, -1})) {
            int k = cnt - carry;
            res -= k;
            cnt -= k;
        }
        res -= carry;
        if (ii + 1 < sz(v) && v[ii + 1].first == nx(c))
            carry = cnt;
        else
            carry = 0;
    }
    cout << res << '\n';
}

```