Leñadores

Time Limit:
1 Sec
Memory Limit:
256Mb
Enviados:
567
Resuelto:
82

Descripción

Hay N árboles ubicados a lo largo de la carretera en puntos con coordenadas x1, x2, ..., xn. Cada árbol tiene su altura hi. Los leñadores pueden cortar un árbol y hacerlo caer hacia la izquierda o hacia la derecha. Después de eso, ocupa uno de los segmentos [xi - hi, xi] o [xi; xi + hi]. El árbol que no se corta ocupa un solo punto con coordenada xi. Los leñadores pueden talar un árbol si el segmento que ocupará el árbol caído no contiene ningún punto ocupado. Los leñadores quieren procesar tantos árboles como sea posible, por lo que tenemos que responder a la pregunta cuál es el número máximo de árboles que podemos talar?

Entrada

La primera linea contiene un numero N que representa el numero de arboles que hay en la carretera  N <= 105

Las siguientes N lineas contienen pares de datos que representa xi y hi     (xi, hi <= 109 )

Nota: Se garantiza que no hay dos arboles situados en la misma coordenada xi

Salida

Imprima un solo número: el número máximo de árboles que se pueden cortar según las reglas dadas.

Ejemplo Entrada

Copy icon
5
1 2
19 1
2 1
5 10
10 9

Ejemplo Salida

Copy icon
3

Ayuda

 Explicacion del caso:

  • talar el arbol de la coordenada 1 a la izquierda — ahora ocupa el segmento [ - 1;1]
  • talar el arbol de la coordenada 2 a la derecha — ahora ocupa el segmento [2;3]
  • no talar el arbol de la coordenada 5 — ocupa el punto 5
  • no talar el arbol de la coordenada 10 — ocupa el punto10
  • talar el arbol de la coordenada 19 a la derecha— ahora ocupa el segmento [19;20]