#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>

#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back

#define N 100005
#define M 200005
#define seed 23333

using namespace std;
const int inf=(int)1e9;
int i,j,m,n,p,k,A[N],B[N],l;
map<pair<int,int>,int>mp;
vector<int>v[M];
int f[2][N],ans,sum[N],size[2],now,last;
int RE()
{
		puts("-1");
		exit(0);
}
int main()
{
		scanf("%d",&n); ans=2*n-2;
		for (i=1;i<=n;++i) 
		{
				scanf("%d%d",&A[i],&B[i]);
				mp[mk(A[i],B[i])]=1;
				if (i!=1&&!A[i]) RE();
				if (i!=2&&!B[i]) RE();
		}
		for (i=1;i<=n;++i)
		{
				if (i!=1&&mp.find(mk(A[i]-1,B[i]))==mp.end()&&
						mp.find(mk(A[i]-1,B[i]-1))==mp.end()&&
						mp.find(mk(A[i]-1,B[i]+1))==mp.end()) RE();
				if (i!=2&&mp.find(mk(A[i],B[i]-1))==mp.end()&&
						mp.find(mk(A[i]-1,B[i]-1))==mp.end()&&
						mp.find(mk(A[i]+1,B[i]-1))==mp.end()) RE();
				v[A[i]+B[i]].pb(A[i]);
		}
		for (i=1;i<=2*n;++i)
				if (v[i].size())
				{
						A[0]=B[0]=0;
						for (j=0;j<(int)v[i].size();++j) A[++A[0]]=v[i][j],B[++B[0]]=v[i][j]; 
						sort(B+1,B+B[0]+1); B[0]=unique(B+1,B+B[0]+1)-(B+1);
						for (j=1;j<=B[0];++j) sum[j]=0;
						for (j=1;j<=A[0];++j) sum[lower_bound(B+1,B+B[0]+1,A[j])-B]++;
						size[0]=size[1]=now=last=0; now=1;
						size[1]=sum[1];
						if (mp.find(mk(B[1]-1,i-B[1]-1))!=mp.end())
						for (j=0;j<=size[now];++j) f[now][j]=size[now]-j;
						else for (j=0;j<=size[now];++j) f[now][j]=0;
						for (j=2;j<=B[0];++j)
						{
								now^=1; last=now^1;
								size[now]=sum[j];
								for (l=0;l<=size[now];++l) f[now][l]=0;
								if (mp.find(mk(B[j]-1,i-B[j]-1))==mp.end())
								{
									  for (l=0;l<=size[last];++l)
									  	 f[now][sum[j]]=max(f[now][sum[j]],f[last][l]+(B[j]-B[j-1]==1)*min(sum[j],l));
								}
								else 
								{
									 int Max=-inf;
									 for (l=0;l<=size[now];++l)
									{
											if (l<=size[last]) Max=max(Max,f[last][l]+(B[j]-B[j-1]==1)*l);
											f[now][l]=Max;
									}
									 Max=-inf;
									 for (l=max(size[last],size[now]);l>=0;--l)
									 {
									 		if (l<=size[last]) Max=max(Max,f[last][l]);
									 		if (l<=size[now])
									 		f[now][l]=max(f[now][l],Max+(B[j]-B[j-1]==1)*l);
									 }
									 for (l=0;l<=size[now];++l)
									 	f[now][l]+=(size[now]-l);
								}
						}
						int Max=0;
						for (j=0;j<=size[now];++j) Max=max(Max,f[now][j]);
						ans-=Max;
				}
		printf("%d\n",ans);
}

### Prompt

Create a solution in Cpp for 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<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>

#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back

#define N 100005
#define M 200005
#define seed 23333

using namespace std;
const int inf=(int)1e9;
int i,j,m,n,p,k,A[N],B[N],l;
map<pair<int,int>,int>mp;
vector<int>v[M];
int f[2][N],ans,sum[N],size[2],now,last;
int RE()
{
		puts("-1");
		exit(0);
}
int main()
{
		scanf("%d",&n); ans=2*n-2;
		for (i=1;i<=n;++i) 
		{
				scanf("%d%d",&A[i],&B[i]);
				mp[mk(A[i],B[i])]=1;
				if (i!=1&&!A[i]) RE();
				if (i!=2&&!B[i]) RE();
		}
		for (i=1;i<=n;++i)
		{
				if (i!=1&&mp.find(mk(A[i]-1,B[i]))==mp.end()&&
						mp.find(mk(A[i]-1,B[i]-1))==mp.end()&&
						mp.find(mk(A[i]-1,B[i]+1))==mp.end()) RE();
				if (i!=2&&mp.find(mk(A[i],B[i]-1))==mp.end()&&
						mp.find(mk(A[i]-1,B[i]-1))==mp.end()&&
						mp.find(mk(A[i]+1,B[i]-1))==mp.end()) RE();
				v[A[i]+B[i]].pb(A[i]);
		}
		for (i=1;i<=2*n;++i)
				if (v[i].size())
				{
						A[0]=B[0]=0;
						for (j=0;j<(int)v[i].size();++j) A[++A[0]]=v[i][j],B[++B[0]]=v[i][j]; 
						sort(B+1,B+B[0]+1); B[0]=unique(B+1,B+B[0]+1)-(B+1);
						for (j=1;j<=B[0];++j) sum[j]=0;
						for (j=1;j<=A[0];++j) sum[lower_bound(B+1,B+B[0]+1,A[j])-B]++;
						size[0]=size[1]=now=last=0; now=1;
						size[1]=sum[1];
						if (mp.find(mk(B[1]-1,i-B[1]-1))!=mp.end())
						for (j=0;j<=size[now];++j) f[now][j]=size[now]-j;
						else for (j=0;j<=size[now];++j) f[now][j]=0;
						for (j=2;j<=B[0];++j)
						{
								now^=1; last=now^1;
								size[now]=sum[j];
								for (l=0;l<=size[now];++l) f[now][l]=0;
								if (mp.find(mk(B[j]-1,i-B[j]-1))==mp.end())
								{
									  for (l=0;l<=size[last];++l)
									  	 f[now][sum[j]]=max(f[now][sum[j]],f[last][l]+(B[j]-B[j-1]==1)*min(sum[j],l));
								}
								else 
								{
									 int Max=-inf;
									 for (l=0;l<=size[now];++l)
									{
											if (l<=size[last]) Max=max(Max,f[last][l]+(B[j]-B[j-1]==1)*l);
											f[now][l]=Max;
									}
									 Max=-inf;
									 for (l=max(size[last],size[now]);l>=0;--l)
									 {
									 		if (l<=size[last]) Max=max(Max,f[last][l]);
									 		if (l<=size[now])
									 		f[now][l]=max(f[now][l],Max+(B[j]-B[j-1]==1)*l);
									 }
									 for (l=0;l<=size[now];++l)
									 	f[now][l]+=(size[now]-l);
								}
						}
						int Max=0;
						for (j=0;j<=size[now];++j) Max=max(Max,f[now][j]);
						ans-=Max;
				}
		printf("%d\n",ans);
}

```