#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <ctime>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 100005;

int n;
pair<int,int> a[maxn];

bool check_1(){
  if(a[1].first!=0||a[2].second!=0||a[2].first!=a[1].second||a[1].second==0)return false;
  for(int i=3;i<=n;i++)
    if(a[i].first==0||a[i].second==0||a[i].first+a[i].second<a[1].first+a[1].second)return false;
  set<pair<int,int>>st;
  for(int i=1;i<=n;i++)st.insert(a[i]);
  for(int i=3;i<=n;i++){
    int cnt=0;
    for(int j=-1;j<=1;j++)
      if(st.find(make_pair(a[i].first-1,a[i].second+j))!=st.end()){
        cnt++;
        break;
      }
    for(int j=-1;j<=1;j++)
      if(st.find(make_pair(a[i].first+j,a[i].second-1))!=st.end()){
        cnt++;
        break;
      }
      if(cnt<2)return false;
  }
  return true;
}

bool cmp(pair<int,int> a,pair<int,int> b){
  int ta = a.first + a.second;
  int tb = b.first + b.second;
  return ta == tb ? a.first < b.first: ta < tb;
}

int cal(){
  int ret=0;
  sort(a+1,a+n+1,cmp);
  map<pair<int,int>,int>mp;
  for(int i=1;i<=n;i++){
    int pos = i;
    vector<pair<int,int>>v;
    v.push_back(a[i]);
    for(int j = i;j<=n;j++){
      if(a[j].first + a[j].second!=a[i].first + a[i].second)break;
      pos = j;
      if(mp.find(a[j])==mp.end())mp[a[j]]=1;
      else mp[a[j]]+=1;
      if(j>i&&a[j]!=a[j-1])v.push_back(a[j]);
    }
    int l = 0;
    for(int j=0;j<v.size();j++){
      int nl = mp[v[j]];
      int nr = nl;
      if(v[j].second==0)nr=0;
      ret+=min(l,nl);
      nl-=l;
      if(nl<0)nl=0;
      if(mp.find(make_pair(v[j].first-1,v[j].second-1))!=mp.end()){
        ret+=min(nl,nr);
        nr -= min(nl,nr);
      }
      l = nr;
      if(l<0)l=0;
      if(j+1<v.size()&&v[j].first+1<v[j+1].first)l=0;
      //cout<<j<<" : "<<ret<<endl;
      //cout<<v[j].first<<","<<v[j].second<<endl;
    }
    i =pos;
  }
  //cout<<ret<<endl;
  return ret;
}

int main() {
   // freopen("in.cpp","r",stdin);
    cin>>n;
    for(int i=1; i<=n; i++) {
        int x,y;
        cin>>x>>y;
        a[i].first = x;
        a[i].second = y;
    }
    if(!check_1()){
      cout<<-1<<endl;
      return 0;
    }
    cout<<2*n-2-cal()<<endl;
    return 0;
}

### Prompt

Your challenge is to write 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 <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <ctime>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 100005;

int n;
pair<int,int> a[maxn];

bool check_1(){
  if(a[1].first!=0||a[2].second!=0||a[2].first!=a[1].second||a[1].second==0)return false;
  for(int i=3;i<=n;i++)
    if(a[i].first==0||a[i].second==0||a[i].first+a[i].second<a[1].first+a[1].second)return false;
  set<pair<int,int>>st;
  for(int i=1;i<=n;i++)st.insert(a[i]);
  for(int i=3;i<=n;i++){
    int cnt=0;
    for(int j=-1;j<=1;j++)
      if(st.find(make_pair(a[i].first-1,a[i].second+j))!=st.end()){
        cnt++;
        break;
      }
    for(int j=-1;j<=1;j++)
      if(st.find(make_pair(a[i].first+j,a[i].second-1))!=st.end()){
        cnt++;
        break;
      }
      if(cnt<2)return false;
  }
  return true;
}

bool cmp(pair<int,int> a,pair<int,int> b){
  int ta = a.first + a.second;
  int tb = b.first + b.second;
  return ta == tb ? a.first < b.first: ta < tb;
}

int cal(){
  int ret=0;
  sort(a+1,a+n+1,cmp);
  map<pair<int,int>,int>mp;
  for(int i=1;i<=n;i++){
    int pos = i;
    vector<pair<int,int>>v;
    v.push_back(a[i]);
    for(int j = i;j<=n;j++){
      if(a[j].first + a[j].second!=a[i].first + a[i].second)break;
      pos = j;
      if(mp.find(a[j])==mp.end())mp[a[j]]=1;
      else mp[a[j]]+=1;
      if(j>i&&a[j]!=a[j-1])v.push_back(a[j]);
    }
    int l = 0;
    for(int j=0;j<v.size();j++){
      int nl = mp[v[j]];
      int nr = nl;
      if(v[j].second==0)nr=0;
      ret+=min(l,nl);
      nl-=l;
      if(nl<0)nl=0;
      if(mp.find(make_pair(v[j].first-1,v[j].second-1))!=mp.end()){
        ret+=min(nl,nr);
        nr -= min(nl,nr);
      }
      l = nr;
      if(l<0)l=0;
      if(j+1<v.size()&&v[j].first+1<v[j+1].first)l=0;
      //cout<<j<<" : "<<ret<<endl;
      //cout<<v[j].first<<","<<v[j].second<<endl;
    }
    i =pos;
  }
  //cout<<ret<<endl;
  return ret;
}

int main() {
   // freopen("in.cpp","r",stdin);
    cin>>n;
    for(int i=1; i<=n; i++) {
        int x,y;
        cin>>x>>y;
        a[i].first = x;
        a[i].second = y;
    }
    if(!check_1()){
      cout<<-1<<endl;
      return 0;
    }
    cout<<2*n-2-cal()<<endl;
    return 0;
}

```