Cho \(n\) đoạn thẳng trên trục Ox, đoạn thứ \(i\) (ký hiệu là \(T_i\)) bắt đầu tại điểm \(x_i\) và có độ dài \(l_i\). Ở mỗi đoạn ta cần chọn ra một điểm đại diện của đoạn đó. Biết rằng không có hai đoạn nào hoàn toàn chứa nhau (nói cách khác, không tồn tại \(i\) và \(j\) khác nhau sau cho \(x_j\leq x_i\) và \(x_i+l_i\leq x_j+l_j\)), bạn hãy lập trình xác định một cách chọn \(n\) điểm đại diện sao cho khoảng cách giữa hai điểm gần nhất là lớn nhất có thể.

Ví dụ, hai hình dưới đây thể hiện hai cách chọn điểm đại diện cho \(6\) đoạn thẳng (điểm đại diện được tô đậm màu đen ở mỗi đoạn màu đỏ). Ở cách chọn đầu tiên, hai điểm gần nhất cách nhau \(20\) đơn vị độ dài. Ở cách chọn thứ nhì, hai điểm gần nhất cách nhau \(25\) đơn vị độ dài.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(2\leq n\leq 10^5\)).

• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa hai số nguyên \(x_i\) và \(l_i\) (\(0\leq x_i\leq 10^9\), \(1\leq l_i\leq 10^9\)).

Example

6
0 67
127 36
110 23
50 51
100 12
158 17

25

6
0 40
10 55
45 28
90 40
83 30
120 30

30

3
0 20
40 10
100 20

50