Bờm chơi một trò chơi đoán số như sau: giả sử số phải tìm là X, Bờm có N manh mối để đoán, manh mối thứ i có dạng chênh lệch giữa X và v[i] không vượt quá d[i]. Bờm muốn nhờ bạn xác định liệu có tồn tại giá trị X thỏa mãn tất cả N manh mối hay không, nếu có thì giá trị X lớn nhất có thể là bao nhiêu.

Input

• Dòng đầu chứa số nguyên N ( 1≤ N ≤100000)

• Dòng tiếp theo, dòng thứ i ghi hai số nguyên v[i] và d[i] (0 ≤ v[i], d[i] ≤10^9)

Output

Ghi ra số nguyên X là giá trị lớn nhất tìm được, số này bằng -1 nếu không tồn tại giá trị X thỏa mãn tất cả các manh mối.

Sample Input

2
1 2
3 2

Sample Output

3

Sample Input

3
2 2
6 2
8 1

Sample Output

-1