#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

int main() {
  int N; scanf("%d", &N);
  static int A[100000], B[100000];
  static pair<int, int> ABtbl[100000];
  static pair<int, int> BAtbl[100000];
  for(int i = 0; i < N; ++i) {
    scanf("%d%d", &A[i], &B[i]);
    ABtbl[i] = make_pair(A[i], B[i]);
    BAtbl[i] = make_pair(B[i], A[i]);
  }
  if(A[0] != 0 || B[1] != 0 || A[1] == 0 || A[1] != B[0]) {
    printf("%d\n", -1);
    return 0;
  }
  sort(ABtbl, ABtbl+N);
  sort(BAtbl, BAtbl+N);
  for(int i = 0; i < N; ++i) {
    if(i != 0 &&
        lower_bound(ABtbl, ABtbl+N, make_pair(A[i]-1, B[i]-1))
        == upper_bound(ABtbl, ABtbl+N, make_pair(A[i]-1, B[i]+1))) {
      printf("%d\n", -1);
      return 0;
    }
    if(i != 1 &&
        lower_bound(BAtbl, BAtbl+N, make_pair(B[i]-1, A[i]-1))
        == upper_bound(BAtbl, BAtbl+N, make_pair(B[i]-1, A[i]+1))) {
      printf("%d\n", -1);
      return 0;
    }
  }
  int count = 2 * (N-1);
  for(int ii = 0; ii < N; ++ii) {
    if(ii > 0 && ABtbl[ii-1] == ABtbl[ii]) continue;
    int a = ABtbl[ii].first;
    int b = ABtbl[ii].second;
    if(lower_bound(ABtbl, ABtbl+N, make_pair(a-1, b+1))
        < upper_bound(ABtbl, ABtbl+N, make_pair(a-1, b+1))) {
      continue;
    }
    int have =
      upper_bound(ABtbl, ABtbl+N, make_pair(a, b))
        - lower_bound(ABtbl, ABtbl+N, make_pair(a, b));
    int rem = have;
    while(true) {
      int capa = have;
      if(lower_bound(ABtbl, ABtbl+N, make_pair(a-1, b-1))
          < upper_bound(ABtbl, ABtbl+N, make_pair(a-1, b-1))) {
        // fprintf(stderr, "(%d, %d) -- %d recyclable edges to (%d, %d)\n",
        //     a, b, rem, a-1, b-1);
        count -= rem;
        capa -= rem;
      }
      ++a;
      --b;
      have =
        upper_bound(ABtbl, ABtbl+N, make_pair(a, b))
          - lower_bound(ABtbl, ABtbl+N, make_pair(a, b));
      if(have == 0) break;
      // fprintf(stderr, "(%d, %d) -- %d recyclable edges to (%d, %d)\n",
      //     a-1, b+1, min(capa, have), a, b);
      count -= min(capa, have);
      rem = have - min(capa, have);
    }
  }
  printf("%d\n", count);
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 <cstdio>
#include <algorithm>
#include <map>
using namespace std;

int main() {
  int N; scanf("%d", &N);
  static int A[100000], B[100000];
  static pair<int, int> ABtbl[100000];
  static pair<int, int> BAtbl[100000];
  for(int i = 0; i < N; ++i) {
    scanf("%d%d", &A[i], &B[i]);
    ABtbl[i] = make_pair(A[i], B[i]);
    BAtbl[i] = make_pair(B[i], A[i]);
  }
  if(A[0] != 0 || B[1] != 0 || A[1] == 0 || A[1] != B[0]) {
    printf("%d\n", -1);
    return 0;
  }
  sort(ABtbl, ABtbl+N);
  sort(BAtbl, BAtbl+N);
  for(int i = 0; i < N; ++i) {
    if(i != 0 &&
        lower_bound(ABtbl, ABtbl+N, make_pair(A[i]-1, B[i]-1))
        == upper_bound(ABtbl, ABtbl+N, make_pair(A[i]-1, B[i]+1))) {
      printf("%d\n", -1);
      return 0;
    }
    if(i != 1 &&
        lower_bound(BAtbl, BAtbl+N, make_pair(B[i]-1, A[i]-1))
        == upper_bound(BAtbl, BAtbl+N, make_pair(B[i]-1, A[i]+1))) {
      printf("%d\n", -1);
      return 0;
    }
  }
  int count = 2 * (N-1);
  for(int ii = 0; ii < N; ++ii) {
    if(ii > 0 && ABtbl[ii-1] == ABtbl[ii]) continue;
    int a = ABtbl[ii].first;
    int b = ABtbl[ii].second;
    if(lower_bound(ABtbl, ABtbl+N, make_pair(a-1, b+1))
        < upper_bound(ABtbl, ABtbl+N, make_pair(a-1, b+1))) {
      continue;
    }
    int have =
      upper_bound(ABtbl, ABtbl+N, make_pair(a, b))
        - lower_bound(ABtbl, ABtbl+N, make_pair(a, b));
    int rem = have;
    while(true) {
      int capa = have;
      if(lower_bound(ABtbl, ABtbl+N, make_pair(a-1, b-1))
          < upper_bound(ABtbl, ABtbl+N, make_pair(a-1, b-1))) {
        // fprintf(stderr, "(%d, %d) -- %d recyclable edges to (%d, %d)\n",
        //     a, b, rem, a-1, b-1);
        count -= rem;
        capa -= rem;
      }
      ++a;
      --b;
      have =
        upper_bound(ABtbl, ABtbl+N, make_pair(a, b))
          - lower_bound(ABtbl, ABtbl+N, make_pair(a, b));
      if(have == 0) break;
      // fprintf(stderr, "(%d, %d) -- %d recyclable edges to (%d, %d)\n",
      //     a-1, b+1, min(capa, have), a, b);
      count -= min(capa, have);
      rem = have - min(capa, have);
    }
  }
  printf("%d\n", count);
  return 0;
}

```