K - ターゲット Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

円の列 C_1, C_2, ..., C_K は各 i に対し C_{i+1} が C_i の strictly に内部にあるときサイズ K のターゲットであるという。 すぬけ君は、円を N 個描いた。i 番目の円は中心が (x_i, 0) であり、半径が r_i である。この中から円をいくつか選んでターゲットを作るとき、ターゲットの最大サイズを求めよ。

Constraints

  • 1 ≤ N ≤ 100000
  • 0 ≤ x_i ≤ 100,000,000
  • 1 ≤ r_i ≤ 100,000,000

Input Format

入力は以下の形式で標準入力から与えられる。
N
x_1 r_1
…
x_N r_N

Output Format

答えを一行に出力せよ。

Sample Input 1

3
1 1
0 3
3 2

Sample Output 1

2
C_1 を二番目の円、C_2 を一番目の円とすればよい。

Sample Input 2

2
1 1
2 2

Sample Output 2

1
円の包含関係は strict である (境界が重なっている場合は内部とはみなさない)。