Problem Description

There is a connected undirected graph with $ N $ vertices, numbered from $ 1 $ to $ N $. The length of each edge is $ 1 $. For each $i\ (1≦i≦N)$, the distance between vertex $ 1 $ and vertex $ i $ is known to be $ A_i $, and the distance between vertex $ 2 $ and vertex $ i $ is known to be $ B_i $. Determine if such a graph exists. If it does, find the minimum number of edges that such a graph can have.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_N $ $ B_N $

Output Format

If a graph satisfying the conditions exists, output the minimum number of edges; otherwise, output -1.

Sample Input and Output

Sample Input #1

4
0 1
1 0
1 1
2 1

Sample Output #1

4

Sample Input #2

3
0 1
1 0
2 2

Sample Output #2

-1

Notes/Hints

Constraints

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

Sample Explanation 1

Two types of graphs are possible as shown below, but the graph on the right has fewer edges. 

Sample Explanation 2

Such a graph does not exist.

见题面 Input 部分

见题面 Output 部分